A Particular Sort

[rar]

So my most recent assignment in school is apparently based on some sort of Children's Game. I never played this game, but...

The assignment requires that I take in any user-defined amount of numbers and use them to make the highest possible integer.

So as an example:

Input: (numbers = 3)
803 97 3

Output:
978033
(sorting it 97, 803, 3)

So the numbers have to stay together...but as you can see, the numbers aren't sorted largest -> smallest, but they are sorted by the way the digits will make the output numbers the largest.

So I've taken input from the user to define the size of an array
scanf("%d", &n);
int Array[n];

And I've sorted the array elements from greatest to least using a simple bubble sort (being the sort we've learned). However, that was just a start. My next step was to check if the first digit is highest, then the second digit...and to of course use a bubble sort to continue to sort it accordingly.

However, the way I was doing it, I had if statements programmed for each interval of possibility. I'd check <10, >10 but <100, >100 but <1000, and so on...and that's only for the first digits. My above examples only included 3 digits, but I have to assume for any possibility, so it could be 4, 5, or 6 digits...

Anyway so I'm lost at this point. Does anyone have any suggestions? Any help would be much appreciated (not necessarily code just a suggested algorithm or method)

[Euphoracle]

Well, you can convert all these numbers to strings and then use a string comparison because strings are compared l->r by digit rather than by value.

The idea here is to change your comparison function, not your sort.

[Alexmula]

yup. comparing strings is the way to go. take a look at the string.h library.

once you are done submit your code to the uva online judge to make sure it works for all cases

[rar]

Euphoracle @ Sat Jan 30, 2010 11:43 am wrote:

Well, you can convert all these numbers to strings and then use a string comparison because strings are compared l->r by digit rather than by value.

The idea here is to change your comparison function, not your sort.

That's genius!! We haven't learned a lot about the string.h library yet, but there's no specifications on how to solve the problem so I'm sure that would be perfect! Thanks!!

Yeah I knew the sorting method would be the same, but I figured if I kept coding for endless possibilities, it wasnt''t efficient coding.

[Euphoracle]

Well the alternative is tricky floating point math involving log base 10 and dividing/flooring by powers of 10 to extract digits... but that's not as straight forward as this is.

[rar]

So I don't know a lot about string comparison yet....
I searched and found this:

code:

int memcmp(const void *s1, const void *s2, size_t n);

Would this be what I want to use for comparing? I read up on it and I think it returns <0, =0, or >0. I don't know how I would use that...

Essentially what I want to do is compare strings to see which one is greater...though is that really what I want to do?

[DtY]

String comparison is really easy. `memcmp` will work, but you need to give it the length of the buffer, `strcmp` will do the same thing, but wont need the length.

I don't know how much you've learned about strings, but here's how they work.

Strings are arrays of `char`s, all you get is the syntax for assigning a string

C:

char myString[] = "Hello, World!";

This will allocate 14 bytes of memory, and fill it with "Hello, World!" followed by a null (character with the value 0).

Because there is no way of getting the length of an array in C, anything working with arrays need to do one of the following:

a) Store the length of the array in the array
b) Have a special value to mark the end of the array
c) Have a fixed length that every array will use
(This list will come up again when you do socket programming)

C uses option `a` for string functions. Pascal, and some similar languages (for example, Turing) used `b`, but was left with the maximum length of strings being 255 characters.

So, when you use double quotes to fill a string, it automatically adds a null at the end of the string. Which works, for strings. This will not work for binary data though, because it could have a null in it. So, you end up with two funtions, `memcmp` which compares blocks of memory and takes the length of them, and `strcmp` which takes two blocks of memory and finds the length before comparing.

http://www.cplusplus.com/reference/clibrary/cstring/strcmp/

[rar]

So I believe that I should use strcmp then, based on what you've explained.

What exactly does the function compare though? And are you saying that if it can't compare "992" and "45" because they aren't the same length? Or am I misunderstanding...

[DtY]

It will compare them the same way that memcmp would compare them, but it will figure out the length.

I am pretty sure that it will only compare up to the shorter of the two strings (and if they're the same up to that point, the shorter one would be less than the longer one).

[rar]

I guess what I mean to ask is...what will they return?

[DtY]

Ah, the same thing as memcmp

if you do strcmp(A, B);
it will return
=0 if A == B
>0 if A > B
<0 if A < B

I think that generally >0 and <0 are 1 and -1 respectively, but I'm not sure if it is guaranteed.

[rar]

Thanks, yeah I found that info in my textbook but I wasn't sure if I was reading it correctly.

So how are those usually used? Like, I'm not sure how to go about using those return values in my assignment...

[Alexmula]

implement it in ur bubblesort algorithm

[DtY]

You'll need to implement a sorting algorithm, bubble sort would be one of the easier ones to do.

When it's sorting, it will be comparing the values, something like (psedocode)

code:

if a > b then     move a above b else if a < b then     move b above a or else     leave them the same

Rather than using a > b, you would use strcmp(a,b)>0, strcmp(a,b)<0 and strcmp(a,b)==0.

There might be a generic sorting algorithm in one of the C headers, I'm not sure, but if there is,

You would give it an array (probably would have to be of pointers, so that everything is the same size, which strings are anyway), and a pointer to a function that will compare two values.

[rar]

Alright so it's been specified to "do the assignment before the midterm" that is approaching, and when I asked him for a hint, he recommended using powers of 10. So I have abandoned the seemingly simpler algorithm of using String comparison and I have resorted to attempting this method of powers of 10. I have inquired on the forum about this before, and I think I have it figured out, but my code does not work properly.

code:

#include <stdio.h> #include <stdlib.h> int main() { puts("number"); int n; scanf("%d", &n); int temp = n; int count; for(count = 0; temp > 10; count++) { temp = temp / 10; } printf("%d\n", temp); int c2; int temp2 = temp; for(c2 = 0; c2 < count; c2++); { temp *= 10; } int result = n - temp; printf("%d\n", result); }

When I input: 320
The code prints
3
290

What I want it to print is:
3
90

What is wrong with my code? I've traced it and it seems to be in order...