Re: Sorting Numbers

From: Markus Kuhn (Markus.Kuhn@cl.cam.ac.uk)
Date: Mon Mar 13 2000 - 14:30:50 EST


"Jonathan Coxhead" wrote on 2000-03-13 18:53 UTC:
> | Correct ordering of at least integer numbers is a trivial
> | extension of the algorithm:
> |
> | - you treat leading zeros as second level entities
> | - you sort digits as first-level entities
> | - you prefix conceptually any substring of digits
> | with a first-level sorting marker that indicates the length of
> | the digit string.
>
> But there's a bug here (never a good sign in a "trivial" algorithm
> :-): it needs an infinite supply of "1st-level sorting markers", i e,
> it assumes that the problem is already solved.

You can easily implement this with a finite number of sorting markers if
you allow arbitrary length strings of sorting markers. Think about how
UTF-8 works again, and then you will see the light.

Think of sorting markers as a code tree. For mathematicians: Koenig's
lemma tells us that a tree with an infinite number of nodes can still
have a finite degree. QED.

For non-mathematician an example code: Imagine sorting markers A-F and
then write an infinite sorted sequence

A
B
C
D
E
F
FA
FB
...
FF
FFA
FFB
...
FFF
FFFA
FFFB
...

and obviously you can continue this game ad infinitum with a very small
number of sorting markers. Use such a scheme in order to efficiently
encode the length of the following digit sequence, and you have what you
need to get numbers sorted correctly with a minimum of additional logic.

Markus

-- 
Markus G. Kuhn, Computer Laboratory, University of Cambridge, UK
Email: mkuhn at acm.org,  WWW: <http://www.cl.cam.ac.uk/~mgk25/>



This archive was generated by hypermail 2.1.2 : Tue Jul 10 2001 - 17:20:59 EDT