outline-style sorting algorithm

[jwsacksteder at ramprecision.com]

Am I understanding correctly that python has an implict notion that position
in a list denotes order of magnitude? Batteries included- Big Win!


-----Original Message-----
From: Max M [mailto:maxm at mxm.dk]
Sent: Monday, April 19, 2004 10:58 AM
To: Jeff Sacksteder
Cc: python-list at python.org
Subject: Re: outline-style sorting algorithm


jwsacksteder at ramprecision.com wrote:
 > I have a need to sort a list of elements that represent sections of a
 > document in dot-separated notation. The built in sort does the wrong 
thing.

Not really. You are giving it a list of strings, and it sort those 
alphabetically. That seems like the right thing to me ;-)

 > This seems a rather complex problem and I was hoping someone smarter 
than me
 > had already worked out the best way to approach this. For example, 
consider
 > the following list-

 >>>>foo
 >
 > ['1.0', '1.0.1', '1.1.1', '1.2', '1.9', '1.10', '1.11', '1.20', '1.20.1',
 > '1.30']

You need to convert them to another datatype first. Your best bet here 
would be a list or a tuple, as they can map directly to your data.

'1.0.1'.split('.') == [1,0,1]

But list are a bit easier here.

foo_as_tuples = [f.split('.') for f in foo]
foo_as_tuples.sort()

Then you must convert it back to strings again.

foo = ['.'.join(f) for f in foo_as_tuples]

There is a standard way of sorting quickly in python, called 
decorate-sort-undecorate. It is allmost the same example as before:


decorated = [(itm.split('.'),itm) for itm in foo]
decorated.sort()
foo = [d[-1] for d in decorated]

regards Max M