473,545 Members | 1,705 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

outline-style sorting algorithm

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?


Jul 18 '05 #1
5 1550
jw**********@ra mprecision.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.s ort()

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
Jul 18 '05 #2
Max M wrote:
jw**********@ra mprecision.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(st r, 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

Jul 18 '05 #3
jw**********@ra mprecision.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.s ort()

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

Jul 18 '05 #4
jw**********@ra mprecision.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.
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

Jul 18 '05 #5
* jw**********@ra mprecision.com (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
Jul 18 '05 #6

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

2
1301
by: Xavier Noria | last post by:
A Google search here for folding Python code in Emacs pointed to outline.el, but when I try to use some *-hide-* commands I get "Wrong type argument: stringp, nil". The header of the file has no introduction. What is the basic configuration for Python and what's the basic usage? -- fxn
10
3065
by: Agent Mulder | last post by:
I feel the need for an outline specifier to facilitate java-style programming.
3
43957
by: NONYA | last post by:
This is driving me crazy. I'm having trouble with how a simple radio button is displayed, in a simple html form. The default has the outline around the radio button shaded gray only in the top left hand side corner and on a white background it doesn't show up very well. I've seen multiple examples of radio buttons that are fully outlined...
4
8493
by: Doors of Perception | last post by:
As you probably know, when you click on a link in MSIE and go to a page, then when you click the "back" button, you see a dotted box outlining the link on which I just clicked. As far as I'm aware, no versions of Opera support this desired capability natively, so I've experimented, as best I could, with using a custom CSS file which...
1
1160
by: John Doe | last post by:
I collapse an outline block, then copy it, then paste it. In my experience, the outline block always expands after the paste. Is their a way to modify the editor's behavior so that an outline block does not automatically expand when pasted into place? Thanks very much in advance.
3
1710
by: msnews.microsoft.com | last post by:
Anyone ever play with Outline views in VS.NET? I'm amazed I never discovered this. None of this was ever discussed in my training. It's a big help to use this with HTML view. View/Synchronize Document Outline -Max
3
1562
by: Kevin L | last post by:
I am dragging Panel controls on a form (run-time). I am looking for a way to show an outline that is the size of the panel so the user can position the panel accurately. Is there a way to show an outline of the panel control as it is moved on the form?
4
2269
by: Rex | last post by:
Hi - I am new to VB.Net/2005, but not VB. I am trying to find an outline or tree - type control for VB.Net/2005 that provides the ability for the User to TYPE in one of the NODES of the outline... AND while typing, that node will visually expand to 2/3/4/etc lines if the User has reached the end of the line. Ideally, I would also like the...
2
1888
by: Joel Byrd | last post by:
I want to get a red outline around different divs on a page when I hover the mouse over them, and then have the red outline disappear on mouse out (basically to indicate that various elements on the page are "active"). Does anyone know how to do this, or know the best way to do this? Any help with this would be fantastic. OPTIONAL...
0
1298
by: 1001 Webs | last post by:
As I read at: http://webpages.charter.net/edreamleo/front.html Leo is... * A general data management environment. Leo shows user-created relationships among any kind of data: computer programs, web sites, etc. * An outlining editor for programmers. Leo embeds the noweb and CWEB markup languages in an outline
0
7393
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language...
0
7653
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. ...
0
7803
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that...
0
7749
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the...
0
5965
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then...
0
4942
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert...
0
3439
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
1871
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
0
695
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.