Velocity Reviews > outline-style sorting algorithm

# outline-style sorting algorithm

jwsacksteder@ramprecision.com
Guest
Posts: n/a

 04-19-2004
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.
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']
>>> foo.sort()
>>> foo

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

Obviously 1.20.1 should be after 1.9 if we look at this as dot-delimited
integers, not as decimal numbers.

Does anyone have pointers to existing code?

Max M
Guest
Posts: n/a

 04-19-2004
http://www.velocityreviews.com/forums/(E-Mail Removed) 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

Max M
Guest
Posts: n/a

 04-19-2004
(E-Mail Removed) 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

Eric Brunel
Guest
Posts: n/a

 04-19-2004
Max M wrote:
> (E-Mail Removed) 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> -

wes weston
Guest
Posts: n/a

 04-19-2004
(E-Mail Removed) 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.
> 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']
>
>>>>foo.sort()
>>>>foo

>
> ['1.0', '1.0.1', '1.1.1', '1.10', '1.11', '1.2', '1.20', '1.20.1', '1.30',
> '1.9']
>
> Obviously 1.20.1 should be after 1.9 if we look at this as dot-delimited
> integers, not as decimal numbers.
>
> Does anyone have pointers to existing code?
>
>
>
>
>
>
>
>

list = ['1.0', '1.0.1', '1.1.1', '1.2', '1.9', '1.10', '1.11', '1.20',
'1.20.1','1.30']

def parse(str):
list = str.split('.')
if len(list) > 0:
x1 = int(list[0])
else:
x1 = -1
if len(list) > 1:
x2 = int(list[1])
else:
x2 = -1
if len(list) > 2:
x3 = int(list[2])
else:
x3 = -1
return x1,x2,x3

def cmp(x1,x2):
w1 = parse(x1)
w2 = parse(x2)
if w1[0] < w2[0]:
return -1
if w1[0] > w2[0]:
return 1

if w1[1] < w2[1]:
return -1
if w1[1] > w2[1]:
return 1

if w1[2] < w2[2]:
return -1
if w1[2] > w2[2]:
return 1

return 0

#---------------------------
if __name__ == "__main__":
list.sort(cmp)
for x in list:
print x

Thorsten Kampe
Guest
Posts: n/a

 04-29-2004
* (E-Mail Removed) (2004-04-19 15:08 +0100)
> 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.
> 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']
>>>> foo.sort()
>>>> foo

> ['1.0', '1.0.1', '1.1.1', '1.10', '1.11', '1.2', '1.20', '1.20.1', '1.30',
> '1.9']
>
> Obviously 1.20.1 should be after 1.9 if we look at this as dot-delimited
> integers, not as decimal numbers.

You need some general approach to avoid the DSU thing:

def funcsort(seq, func):
""" sort seq by func(item) """
seq = seq[:]
seq.sort(lambda x, y: cmp(func(x), func(y)))
return seq

funcsort(foo, lambda x: map(int, x.split('.')))

Thorsten

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Bapaiah Katepalli VHDL 1 06-23-2006 04:50 PM yee young han C++ 2 05-22-2005 04:51 PM Wahoo C++ 5 05-19-2004 10:22 AM Terry Reedy Python 5 04-20-2004 01:59 PM Ahmed Moustafa Java 0 11-15-2003 06:35 AM