CODEWITHSUNDEEP
sorting
Inquest
Inquest

Reputation: 113

Using a sorting function for numerical sorting

Suppose I have an "oracle" which sorts as follows:

1, 3, 2000, 11, 17, 20

Becomes

1, 11, 17, 20, 2000, 3

(I don't what this mechanism is called). This is akin to UNIX's sort command (without the -n).

I remember Windows used to sort filenames like this prior to Windows XP

Now, I have a bunch of numbers and this sort oracle and I want to sort the numbers numerically, how can I pre-process the numbers such that the sort oracle returns the correct order.

So, is there a function f() which takes in these numbers such that

sort f([1,3,2000,11,17,20])

would return the correct order.

The problem is, we need to sort a bunch of numbers numerically on a system where the only sort available is the sort procedure I described above.

Upvotes: 1

Views: 50

Answers (2)

prokilomer
prokilomer

Reputation: 252

  1. Sort the numbers using this "oracle" sort function, resulting in a list of numbers called e.g.: L.
  2. Remove all single-digit numbers from L, resulting in a list of numbers L1, and create a new list of numbers with the single-digit numbers in the same order as they were in L, resulting in a list of numbers S (if there are no single digit numbers in L, S is going to be empty).
  3. Remove all double-digit numbers from L1, resulting in a list of numbers L2, and append the double-digit numbers in the same order they were in L1 to S (if there are no double-digit numbers in L, L1 remains the same as L and no number is appended to S).
  4. ...
  5. Remove all n-digit numbers from Ln-1, resulting in an empty list of numbers, and append the n-digit numbers in the same order they were in Ln-1 to S.
  6. Now S contains the numerically sorted list of numbers, using only the "oracle" sort function and a function that returns the number of digits of a number, which hopefully your system has.

Of course, you do not need to create a new list of numbers Lk as you remove all k-digit numbers from Lk-1 if the "oracle" sorted list L is mutable.

Upvotes: 0

John Kugelman
John Kugelman

Reputation: 361899

This is called a lexicographical sort. You can pad the numbers with 0s so they all have the same number of digits to get it to behave like a numerical sort. For instance, use a %04d format code with printf.

Upvotes: 2

Related Questions