sort a number highest to lowest

[rhitz1218]

Hi,

I'm trying to create a function that will sort a number's digits
from highest to lowest.

For example

1000 - will become 0001

or 1234 to 4321

Is it better to covert the number to a string first then sort? or
is there a better way to do it?
I just need some clues on how to do it. I've tried to search some
materials on how to do it but I only saw how to sort a 'LIST' but not
just a number.
Thanks for the help

 

[Ian Collins]

Hi,

I'm trying to create a function that will sort a number's digits
from highest to lowest.

For example

1000 - will become 0001

or 1234 to 4321

Is it better to covert the number to a string first then sort? or
is there a better way to do it?

Think again about what you are attempting to sort - the decimal
representation of a binary number. So you aren't sorting the number,
but a textual representation of it. The textual representation is a .....

I just need some clues on how to do it. I've tried to search some
materials on how to do it but I only saw how to sort a 'LIST' but not
just a number.

If you consider what you are sorting, you will see the list.

 

[Richard Heathfield]

(e-mail address removed) said:

Hi,

I'm trying to create a function that will sort a number's digits
from highest to lowest.

For example

1000 - will become 0001

or 1234 to 4321

Is it better to covert the number to a string first then sort? or
is there a better way to do it?

Buckets, my dear chap! Buckets! The world's fastest sorting technique this
side of Lucksort!

I just need some clues on how to do it. I've tried to search some
materials on how to do it but I only saw how to sort a 'LIST' but not
just a number.

Presuming you are dealing only with digits in base N, you can define an
array of N digits, and clear it down to all 0s. If N is a constant integer
expression (or if you are using C99) you can do this:

unsigned long digit[N] = {0};

Now iterate through the number, modding with N. Let's first deal with the
silly case:

if(n == 0)
{
++digit[0];
}
else
{
/* and now we count digits */
while(digit > 0)
{
++digit[n % N];
digit /= N;
}
}

You now have your digit count, and it remains only to iterate through your
array, printing out the digits in whichever order it seems best to you,
making sure you print each the appropriate number of times.

 

[Sourcerer]

Hi,

I'm trying to create a function that will sort a number's digits
from highest to lowest.

For example

1000 - will become 0001

You mean 1000 will stay 1000?

or 1234 to 4321

Is it better to covert the number to a string first then sort? or
is there a better way to do it?
I just need some clues on how to do it. I've tried to search some
materials on how to do it but I only saw how to sort a 'LIST' but not
just a number.
Thanks for the help

There is a number of solutions. If you don't like to sort too much, and your
number is an integer, you could always do the following: If your number is in
base N, then make an array of integers which is N elements long (and initially
all elements are 0).

Now take your number and do a mod N on it. The result is the last digit of that
number. Let's say the digit is X. Increase the X-th element of your array by 1.
Now divide the original number by N. Since your number and N are both integers,
what you will do is remove the last digit. Now do the same for the other digits
in a loop, until what is left of your number is 0.

Now you will have an array with its elements telling you how many of each digit
there is. Define Y as integer and set it to 1. Iterate through the array. If the
current element is > 0, decrease it by 1 and do:

result += X * Y;
Y *= N;

Where X is the current element of the array (not its value, but its position in
that array). I assume 'result' is equal to 0 before this. Do this until the X-th
element is = 0.
When these two loops are done, variable 'result' will contain your result.

--
"It is easy in the world to live after the world's oppinion; it easy in solitude
to live after our own; but the great man is he who in the midst of the crowd
keeps with perfect sweetness the independence of solitude."
Ralph Waldo Emerson, Self-reliance 1841
http://pinpoint.wordpress.com/

 

[Richard Heathfield]

Sourcerer said:

Now you will have an array with its elements telling you how many of each
digit there is. Define Y as integer and set it to 1. Iterate through the
array. If the current element is > 0, decrease it by 1 and do:

result += X * Y;
Y *= N;

You don't need to do this, and indeed it is fraught with peril. Consider,
for example, 16-bit ints and an input of 12789. The required output is
98721, but that won't fit in a 16-bit int. (For 32-bit ints, the same
problem exists - just pick a bigger example.)

There is no need to calculate. You can simply iterate through the array,
printing the appropriate number of digits in each bucket as you go.

 

[rhitz1218]

There is no need to calculate. You can simply iterate through the array,
printing the appropriate number of digits in each bucket as you go.

Thanks. I was able to print the numbers in the array and was able to
sort them in ascending and descending order. Now I would like to print
these integers as one int variable, so I was thinking of concatenating
the integers (like a string) then convert them to integer (atoi)..

But I'm not really quite sure how I can concatenate these array of
integers, Any ideas?
how about the sprintf?

Thanks again for the help.

 

[Sourcerer]

Sourcerer said:

<duplicate of my solution snipped>

Sorry about that, I didn't read it.

You don't need to do this, and indeed it is fraught with peril. Consider,
for example, 16-bit ints and an input of 12789. The required output is
98721, but that won't fit in a 16-bit int. (For 32-bit ints, the same
problem exists - just pick a bigger example.)

There is no need to calculate. You can simply iterate through the array,
printing the appropriate number of digits in each bucket as you go.

True. It wouldn't be perilous, I believe it will just give an incorrect result.
I was thinking that an integer must hold the answer, but now I see this isn't
specified, it only says to sort. You can always define your own type, though,
and functions to deal with them.

--
"It is easy in the world to live after the world's oppinion; it easy in solitude
to live after our own; but the great man is he who in the midst of the crowd
keeps with perfect sweetness the independence of solitude."
Ralph Waldo Emerson, Self-reliance 1841
http://pinpoint.wordpress.com/

 

[santosh]

Thanks. I was able to print the numbers in the array and was able to
sort them in ascending and descending order. Now I would like to print
these integers as one int variable, so I was thinking of concatenating
the integers (like a string) then convert them to integer (atoi)..

But I'm not really quite sure how I can concatenate these array of
integers, Any ideas?
how about the sprintf?

Please provide attributions.

It's not clear what you want to do. Do you want to print the sum of all
the integers in the array? If so, that ought to be obvious.

On the other hand, do you want to print the integers as big string, one
after the other. If so, you can do:

for(counter = 0; counter < elements_in_array; counter++) printf("%d",
array[counter]);
fflush(stdout);

 

[Sourcerer]

Thanks. I was able to print the numbers in the array and was able to
sort them in ascending and descending order. Now I would like to print
these integers as one int variable, so I was thinking of concatenating
the integers (like a string) then convert them to integer (atoi)..

But I'm not really quite sure how I can concatenate these array of
integers, Any ideas?
how about the sprintf?

Thanks again for the help.

So, the result must be an int variable, or do you just want to print it out?
As already pointed out by Richard, you can't do the primer safely, because of
the possible overflow.
The latter, you can do by making the array of characters instead of an array of
integers, and make sure that you are adding '0' to each value you are entering
into an array. Be careful if N (base) is larger than 10, because then you need
to add '0' to digits 0-9, and 'A' for the rest (I assume you won't be going
higher than base 16 - although this would support base 36). After this is done,
you can print it out as string (but don't forget about the delimiter!).
If this is not satisfactory, there are other, but significantly more complicated
solutions.

--
"It is easy in the world to live after the world's oppinion; it easy in solitude
to live after our own; but the great man is he who in the midst of the crowd
keeps with perfect sweetness the independence of solitude."
Ralph Waldo Emerson, Self-reliance 1841
http://pinpoint.wordpress.com/

 

[August Karlstrom]

(e-mail address removed) skrev:

I'm trying to create a function that will sort a number's digits
from highest to lowest.

For example

1000 - will become 0001

or 1234 to 4321

Is it better to covert the number to a string first then sort? or
is there a better way to do it?
I just need some clues on how to do it. I've tried to search some
materials on how to do it but I only saw how to sort a 'LIST' but not
just a number.
Thanks for the help

Here's one way to do it:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int cmp(const void *p, const void *q)
{
char a = *((char *) p), b = *((char *) q);

if (a < b) { return -1; }
else if (a == b) { return 0; }
else { return 1; }
}


int main(int argc, char **argv)
{
int len; char *buf;

if (argc != 2) {
fprintf(stderr, "Error: one integer parameter required");
exit(EXIT_FAILURE);
}
len = strlen(argv[1]);
buf = malloc(len + 1);
strcpy(buf, argv[1]);
qsort(buf, len, 1, cmp);
printf("%s\n", buf);
return 0;
}


August

 

[rhitz1218]

So, the result must be an int variable, or do you just want to print it out?
As already pointed out by Richard, you can't do the primer safely, because of
the possible overflow.
The latter, you can do by making the array of characters instead of an array of
integers, and make sure that you are adding '0' to each value you are entering
into an array. Be careful if N (base) is larger than 10, because then you need
to add '0' to digits 0-9, and 'A' for the rest (I assume you won't be going
higher than base 16 - although this would support base 36). After this is done,
you can print it out as string (but don't forget about the delimiter!).
If this is not satisfactory, there are other, but significantly more complicated
solutions.

My apologies for not making my question clear. Basically what I really
wanted to accomplish is for a 4-digit number for ex:

1342

I would like to sort it from highest to lowest, then from lowest to
highest, therefore that will give me

4321
1234

then I would need to subtract the lower number from the higher number..

So far I was able to arrange the numbers from highest to lowest and
vice versa but I used integer array.. So I have:

(sorted array)
array[0] = 1
array[1] = 2
array[2] = 3
array[3] = 4

I wonder if i can just compare the two integer arrays, then subtract
the lower int array from the higher int array..

I'll try that and see if will work..

Appreciate if somebody will give me some clues too..

Thanks...

 

[santosh]

My apologies for not making my question clear. Basically what I really
wanted to accomplish is for a 4-digit number for ex:

1342

I would like to sort it from highest to lowest, then from lowest to
highest, therefore that will give me

4321
1234

then I would need to subtract the lower number from the higher number..

So far I was able to arrange the numbers from highest to lowest and
vice versa but I used integer array.. So I have:

(sorted array)
array[0] = 1
array[1] = 2
array[2] = 3
array[3] = 4

The easiest thing to do is to convert each array to an integer value
and subtract the lower from the higher. For example:

long high2low = strtol(array_descending, NULL, 0);
long low2high = strtol(array_ascending, NULL, 0);
long diff = high2low - low2high;
printf("%ld\n", diff);

Here array_descending and array_ascending are your two arrays, containg
the number in it's two sorted forms, as a sequence of characters.
strtol() converts them to a long value. Note that in your actual code,
you'll want to check strtol() for failure.

 

[Richard]

(e-mail address removed) said:

Hi,

I'm trying to create a function that will sort a number's digits
from highest to lowest.

For example

1000 - will become 0001

or 1234 to 4321

Is it better to covert the number to a string first then sort? or
is there a better way to do it?

Buckets, my dear chap! Buckets! The world's fastest sorting technique this
side of Lucksort!

I just need some clues on how to do it. I've tried to search some
materials on how to do it but I only saw how to sort a 'LIST' but not
just a number.

Presuming you are dealing only with digits in base N, you can define an
array of N digits, and clear it down to all 0s. If N is a constant integer
expression (or if you are using C99) you can do this:

unsigned long digit[N] = {0};

Now iterate through the number, modding with N. Let's first deal with the
silly case:

if(n == 0)
{
++digit[0];
}
else
{
/* and now we count digits */
while(digit > 0)
n>0

{
++digit[n % N];
digit /= N;
n/=N;

}
}

You now have your digit count, and it remains only to iterate through your
array, printing out the digits in whichever order it seems best to you,
making sure you print each the appropriate number of times.

 

[Richard Heathfield]

August Karlstrom said:

int cmp(const void *p, const void *q)
{
char a = *((char *) p), b = *((char *) q);

Discarding const...

int main(int argc, char **argv)
{
int len; char *buf;

if (argc != 2) {
fprintf(stderr, "Error: one integer parameter required");
exit(EXIT_FAILURE);
}
len = strlen(argv[1]);

....signed/unsigned mismatch...

buf = malloc(len + 1);
strcpy(buf, argv[1]);

....and failing to check malloc's return value before relying on it for
memory. Oopsie.

 

[August Karlstrom]

Richard Heathfield skrev:

August Karlstrom said:

int cmp(const void *p, const void *q)
{
char a = *((char *) p), b = *((char *) q);

Discarding const...

int main(int argc, char **argv)
{
int len; char *buf;

if (argc != 2) {
fprintf(stderr, "Error: one integer parameter required");
exit(EXIT_FAILURE);
}
len = strlen(argv[1]);

...signed/unsigned mismatch...

buf = malloc(len + 1);
strcpy(buf, argv[1]);

...and failing to check malloc's return value before relying on it for
memory. Oopsie.

OK, thanks for the remarks.

And here is the corrected version:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static int cmp(const void *p, const void *q)
{
char a = *((const char *) p), b = *((const char *) q);

if (a < b) { return -1; }
else if (a == b) { return 0; }
else { return 1; }
}


int main(int argc, char **argv)
{
size_t len; char *buf;

if (argc != 2) {
fprintf(stderr, "Error: one parameter required");
exit(EXIT_FAILURE);
}
len = strlen(argv[1]);
buf = malloc(len + 1);
if (!buf) {
fprintf(stderr, "Error: malloc failed");
exit(EXIT_FAILURE);
}
strcpy(buf, argv[1]);
qsort(buf, len, 1, cmp);
printf("%s\n", buf);
free(buf);
return 0;
}


August

 

[Richard Heathfield]

Richard said:

/* and now we count digits */
while(digit > 0)
n>0

Ouch!

{
++digit[n % N];
digit /= N;

n/=N;

Ouch^2!

Thanks. Er, twice.

When did I write that? As in, what time of day?

<checks>

Bleargh!

 

[rhitz1218]

The easiest thing to do is to convert each array to an integer value
and subtract the lower from the higher. For example:

long high2low = strtol(array_descending, NULL, 0);
long low2high = strtol(array_ascending, NULL, 0);
long diff = high2low - low2high;
printf("%ld\n", diff);

Here array_descending and array_ascending are your two arrays, containg
the number in it's two sorted forms, as a sequence of characters.
strtol() converts them to a long value. Note that in your actual code,
you'll want to check strtol() for failure.

but my array_descending and array_ascending are both ints, to use the
strtol, isn't they have to be strings? plus in my output, i want it to
be an integer too, because I will have to perform another operation for
it:

FYI:
I'm trying to create a program that will find a fixed point of a
number, for example:
the number 321:

So the process will be:
321 - 123 = 198
198 - 189 = 792
963 - 369 = 594
954 - 459 = 495
954 - 459 = 495 ===> fixed point..

i was able to have to do desc and asc part, now just a matter of doing
the subraction, getting the answer..
thanks a lot

 

[santosh]

but my array_descending and array_ascending are both ints, to use the
strtol, isn't they have to be strings? plus in my output, i want it to
be an integer too, because I will have to perform another operation for
it:

Well, you need to convert the integer array into an integer. Do
something like:

int value = 0, counter, digit_pos = 0;

/* Find the last meaningful element of the array. For example if your
array has five elements and holds the values arr[0] == 4, arr[1] == 3,
arr[2] == 2, arr[3] == 1, arr[4] == garbage_value, then the last
meaning full element is 3. */

for(counter = last_meaningful_element; counter >= 0; counter++,
digit_pos++)
value += array[counter] * pow(10, digit_pos);

After the loop is complete, value holds the integer value represented
by the array elements. Do the same for both arrays and then perform
your subtraction.