**Next message:**Kenneth Whistler: "Re: DIN 5007, Swiss Sorting"**Previous message:**Markus Kuhn: "Re: Charlemagne et al."**Maybe in reply to:**Markus Kuhn: "Re: Sorting Numbers"**Next in thread:**Kenneth Whistler: "Re: Sorting Numbers"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]**Mail actions:**[ respond to this message ] [ mail a new topic ]

"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/>

**Next message:**Kenneth Whistler: "Re: DIN 5007, Swiss Sorting"**Previous message:**Markus Kuhn: "Re: Charlemagne et al."**Maybe in reply to:**Markus Kuhn: "Re: Sorting Numbers"**Next in thread:**Kenneth Whistler: "Re: Sorting Numbers"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]**Mail actions:**[ respond to this message ] [ mail a new topic ]

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