outline-style sorting algorithm

[Eric Brunel]

Max M wrote:
> 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]
[snip]

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

So the int's are still represented as strings and it does not solve the OP's 
problem:

 >>> foo = ['1.0', '1.0.1', '1.1.1', '1.2', '1.9', '1.10', '1.11', '1.20',
'1.20.1', '1.30']
 >>> bar = [x.split('.') for x in foo]
 >>> bar
[['1', '0'], ['1', '0', '1'], ['1', '1', '1'], ['1', '2'], ['1', '9'], ['1', 
'10'], ['1', '11'], ['1', '20'], ['1', '20', '1'], ['1', '30']]
 >>> bar.sort()
 >>> bar
[['1', '0'], ['1', '0', '1'], ['1', '1', '1'], ['1', '10'], ['1', '11'], ['1', 
'2'], ['1', '20'], ['1', '20', '1'], ['1', '30'], ['1', '9']]

And the 1.20.something are still before 1.9

What you need to do is explicitely convert to integers the strings in the list 
resulting from the split. Here is the shortest way to do it

 >>> bar = [map(int, x.split('.')) for x in foo]
 >>> bar
[[1, 0], [1, 0, 1], [1, 1, 1], [1, 2], [1, 9], [1, 10], [1, 11], [1, 20], [1, 
20, 1], [1, 30]]

Now you can sort:

 >>> bar.sort()
 >>> bar
[[1, 0], [1, 0, 1], [1, 1, 1], [1, 2], [1, 9], [1, 10], [1, 11], [1, 20], [1, 
20, 1], [1, 30]]

Hooray! We've got the result we wanted. Now, convert integers back to string and 
re-join everything:

 >>> foo = ['.'.join(map(str, x)) for x in bar]
 >>> foo
['1.0', '1.0.1', '1.1.1', '1.2', '1.9', '1.10', '1.11', '1.20', '1.20.1', '1.30']

That's what we expected...

HTH
-- 
- Eric Brunel <eric (underscore) brunel (at) despammed (dot) com> -
PragmaDev : Real Time Software Development Tools - http://www.pragmadev.com