How can I sort numbers lexicographically?

Question

Here is the scenario.

I am given an array 'A' of integers. The size of the array is not fixed. The function that I am supposed to write may be called once with an array of just a few integers while another time, it might even contain thousands of integers. Additionally, each integer need not contain the same number of digits.

I am supposed to 'sort' the numbers in the array such that the resulting array has the integers ordered in a lexicographic manner (i.e they are sorted based on their string representations. Here "123" is the string representation of 123). Please note that the output should contain integers only, not their string equivalents.

For example: if the input is:

[ 12 | 2434 | 23 | 1 | 654 | 222 | 56 | 100000 ]

Then the output should be:

[ 1 | 100000 | 12 | 222 | 23 | 2434 | 56 | 654 ]

My initial approach: I converted each integer to its string format, then added zeros to its right to make all the integers contain the same number of digits (this was the messy step as it involved tracking etc making the solution very inefficient) and then did radix sort. Finally, I removed the padded zeros, converted the strings back to their integers and put them in the resulting array. This was a very inefficient solution.

I've been led to believe that the solution doesn't need padding etc and there is a simple solution where you just have to process the numbers in some way (some bit processing?) to get the result.

What is the space-wise most efficient solution you can think of? Time-wise?

If you are giving code, I'd prefer Java or pseudo-code. But if that doesn't suit you, any such language should be fine.

Answer 1

Executable pseudo-code (aka Python): thenumbers.sort(key=str). Yeah, I know that using Python is kind of like cheating -- it's just too powerful;-). But seriously, this also means: if you can sort an array of strings lexicographically, as Python's sort intrinsically can, then just make the "key string" out of each number and sort that auxiliary array (you can then reconstruct the desired numbers array by a str->int transformation, or by doing the sort on the indices via indirection, etc etc); this is known as DSU (Decorate, Sort, Undecorate) and it's what the key= argument to Python's sort implements.

In more detail (pseudocode):

1. allocate an array of char** aux as long as the numbers array
2. for i from 0 to length of numbers-1, aux[i]=stringify(numbers[i])
3. allocate an array of int indices of the same length
4. for i from 0 to length of numbers-1, indices[i]=i
5. sort indices, using as cmp(i,j) strcmp(aux[i],aux[j])
6. allocate an array of int results of the same length
7. for i from 0 to length of numbers-1, results[i]=numbers[indices[i]]
8. memcpy results over numbers
9. free every aux[i], and also aux, indices, results

Answer 2

Since you mentioned Java is the actual language in question:

You don't need to convert to and from strings. Instead, define your own comparator and use that in the sort.

Specifically:

Comparator<Integer> lexCompare = new Comparator<Integer>(){
   int compareTo( Integer x, Integer y ) {
      return x.toString().compareTo( y.toString() );
   }
};

Then you can sort the array like this:

int[] array = /* whatever */;
Arrays.sort( array, lexCompare );

(Note: The int/Integer mismatch works automatically through auto-boxing)