Sort N numbers in numerical order

Question

A numerical number N is indicated, for example. [1 to 100], sort the numbers in numerical order (ie). For numbers from 1 to 100, the sorted output satchel will be 1 10 100 11 12 13., 19 2 20 21 ..... 99

This is similar to the Radix Sort, but only that the numbers are sorted in reverse order to what will be done in the regular Radix Sort.

I tried to save all the numbers in each number as a linked list for faster work, but this leads to a lot of space complexity.

I need a working algorithm for the question.

Of all the answers, Converting to Strings is an option, but is there any other way to do this? The string sorting algorithm mentioned above may also be specified.

Answer 1

Use whatever sorting algorithm you like, but compare numbers as strings, not numbers. This is mainly lexicographic sorting of regular numbers. Here's an example of sorting gnome in C:

#include <stdlib.h> #include <string.h> void sort(int* array, int length) { int* iter = array; char buf1[12], buf2[12]; while(iter++ < array+length) { if(iter == array || (strcmp(itoa(*iter, &buf1, 10), itoa(*(iter-1), &buf2, 10) >= 0) { iter++; } else { *iter ^= *(iter+1); *(iter+1) ^= *iter; *iter ^= *(iter+1); iter--; } } } 

Of course, this requires the non-standard itoa function in stdlib.h . A more standard alternative would be to use sprintf , but this makes the code a bit more cluttered. You might be better off converting the entire array to strings first and then sorting and then converting back.

Edit: For reference, the corresponding bit here is strcmp(itoa(*iter, &buf1, 10), itoa(*(iter-1), &buf2, 10) >= 0 , which replaces *iter >= *(iter-1) .

Answer 2

I have a solution, but not quite an algorithm. All you have to do is convert all numbers to strings and sort them as strings.

Answer 3

Here's how you can do it with a recursive function (the code is in Java):

 void doOperation(List<Integer> list, int prefix, int minimum, int maximum) { for (int i = 0; i <= 9; i++) { int newNumber = prefix * 10 + i; if (newNumber >= minimum && newNumber <= maximum) { list.add(newNumber); } if (newNumber > 0 && newNumber <= maximum) { doOperation(list, newNumber, minimum, maximum); } } } 

You call it this way:

 List<Integer> numberList = new ArrayList<Integer>(); int min=1, max =100; doOperation(numberList, 0, min, max); System.out.println(numberList.toString()); 

---

EDIT:

I translated my C ++ code here :

 #include <stdio.h> void doOperation(int list[], int &index, int prefix, int minimum, int maximum) { for (int i = 0; i <= 9; i++) { int newNumber = prefix * 10 + i; if (newNumber >= minimum && newNumber <= maximum) { list[index++] = newNumber; } if (newNumber > 0 && newNumber <= maximum) { doOperation(list, index, newNumber, minimum, maximum); } } } int main(void) { int min=1, max =100; int* numberList = new int[max-min+1]; int index = 0; doOperation(numberList, index, 0, min, max); printf("["); for(int i=0; i<max-min+1; i++) { printf("%d ", numberList[i]); } printf("]"); return 0; } 

Basically, the idea is this: for each digit (0-9) I add it to the array if it is between minimum and maximum . Then I call the same function with this number as a prefix. It does the same: for each digit, it adds it to the prefix ( prefix * 10 + i ), and if it is between the limits, it adds it to the array. It stops when newNumber greater than the maximum.

Answer 4

I think that if you convert numbers to a string, you can use string comparison to sort them. you can use alghorighm sort for it.

"1" "10" "100" "11" ...

Answer 5

Optimize the way numbers are stored: use the binary-coded decimal (BCD) type , which gives easy access to a specific digit. . Then you can use your current algorithm, which Steve Jessop correctly identified as the most significant sorting of number notation .

I tried to save all the numbers in each number as a linked list for faster, but this leads to a lot of space complexity.

Saving each digit in a linked list consumes space in two ways:

• A digit (0-9) only requires 4 bits of memory to store, but you probably use 8 to 64 bits. The char or short accepts 8 bits, and int can accept up to 64 bits. It is from 2X to 16X more memory than the optimal solution!
• Linked lists add extra unnecessary memory overhead. For each digit, you need an additional 32 - 64 bits to save the memory address of the next link. Again, this increases the amount of memory needed for each digit by 8X to 16X.

Storage with more economical BCD memory sequentially shifts in memory:

• BCD uses only 4 bits per digit.
• Store the numbers in an adjacent memory block as an array. This eliminates the need to store memory addresses. You do not need linked lists to easily insert / remove from the middle. If you need the ability to grow numbers to an unknown length, there are other abstract data types that can do this with much less overhead. For example, vector .

One option, if other operations, such as adding / multiplying, are not important, is to allocate enough memory to store each BCD digit plus one BCD delimiter. The BCD terminator can be any 4-bit combination that is not used to represent a BCD digit (for example, binary 1111 ). However, saving this method will make other operations, such as addition and multiplication, more complicated.

Note that this is very similar to the idea of ​​converting to strings and lexicographically sorting those strings. Entire elements are stored in binary form (base 2) on the computer. Storage in a BCD is more like base 10 (base 16, in fact, but 6 combinations are ignored), and strings are like base 256. Strings will use about twice as much memory, but there are already efficient functions written to sort the strings. BCD will probably require the development of a custom BCD type for your needs.

Answer 6

Edit: I missed that this is an adjacent range. In this case, all the answers that say about sorting the array are incorrect (including your idea stated in the question that it looks like sorting a number), and the correct answer is True Soft.

just like Radix Sort, but just that the numbers are sorted in reverse order

Well noticed :-) If you actually do it in a strange way, it is called radix MSD sorting.

http://en.wikipedia.org/wiki/Radix_sort#Most_significant_digit_radix_sorts

You can implement one very simply or with a lot of high technology and fanfare. In most programming languages, your specific example has some minor difficulties. Extracting decimal digits from the natural integer storage format is not a particularly fast operation. You can ignore this and see how long it ends (recommended), or you can add even more fanfare by converting all numbers to decimal strings before sorting.

Of course, you do not need to implement it as radix sorting: you can use the comparison sorting algorithm with the corresponding comparator. For example, in C, it is suitable for use with qsort (unless I messed it up):

 int lex_compare(void *a, void *b) { char a_str[12]; // assuming 32bit int char b_str[12]; sprintf(a_str, "%d", *(int*)a); sprintf(b_str, "%d", *(int*)b); return strcmp(a_str,b_str); } 

Not very effective, since it repeats a lot of work, but simply.

Answer 7

If you do not want to convert them to strings, but you have enough space to store an additional copy of the list, I would save the greatest power ten times less than the element in the copy. This is probably the easiest thing to do with the loop. Now call the original array x and authorities ten y .

 int findPower(int x) { int y = 1; while (y * 10 < x) { y = y * 10; } return y; } 

You can also calculate them directly.

 y = exp10(floor(log10(x))); 

but I suspect that iteration may be faster than floating point conversions to and from it.

To compare the elements i th and j th

 bool compare(int i, int j) { if (y[i] < y[j]) { int ti = x[i] * (y[j] / y[i]); if (ti == x[j]) { return (y[i] < y[j]); // the compiler will optimize this } else { return (ti < x[j]); } } else if (y[i] > y[j]) { int tj = x[j] * (y[i] / y[j]); if (x[i] == tj) { return (y[i] < y[j]); // the compiler will optimize this } else { return (x[i] < tj); } } else { return (x[i] < x[j]; } } 

What is being done here, we multiply the smaller number by the corresponding power of ten, so that the two numbers have an equal number of digits, and then compare them. if the two changed numbers are equal, then compare the lengths of the digits.

If you don't have space to store y arrays, you can compute them with every comparison.

In general, you are most likely to use pre-optimized digit conversion procedures.