sort the list

[Shi Mu]

I have a list like [[1,4],[3,9],[2,5],[3,2]]. How can I sort the list
based on the second value in the item?
That is,
I want the list to be:
[[3,2],[1,4],[2,5],[3,9]]

[Daniel Schüle]

Shi Mu wrote:

I have a list like [[1,4],[3,9],[2,5],[3,2]]. How can I sort the list
based on the second value in the item?
That is,
I want the list to be:
[[3,2],[1,4],[2,5],[3,9]]

lst = [[1,4],[3,9],[2,5],[3,2]]
lst [[1, 4], [3, 9], [2, 5], [3, 2]]

lst.sort(cmp = lambda x,y: cmp(x[1], y[1]))
lst [[3, 2], [1, 4], [2, 5], [3, 9]]

works for Python 2.4
in earlier Pythons just let cmp = .. away

Regards, Daniel

[Daniel Schüle]

Shi Mu wrote:

I have a list like [[1,4],[3,9],[2,5],[3,2]]. How can I sort the list
based on the second value in the item?
That is,
I want the list to be:
[[3,2],[1,4],[2,5],[3,9]]

lst = [[1,4],[3,9],[2,5],[3,2]]
lst [[1, 4], [3, 9], [2, 5], [3, 2]]

lst.sort(cmp = lambda x,y: cmp(x[1], y[1]))
lst [[3, 2], [1, 4], [2, 5], [3, 9]]

works for Python 2.4
in earlier Pythons just let cmp = .. away

Regards, Daniel

[Shi Mu]

On 11/21/05, Daniel Schüle <uv**@rz.uni-karlsruhe.de> wrote:

Shi Mu wrote:

I have a list like [[1,4],[3,9],[2,5],[3,2]]. How can I sort the list
based on the second value in the item?
That is,
I want the list to be:
[[3,2],[1,4],[2,5],[3,9]]

>>> lst = [[1,4],[3,9],[2,5],[3,2]]
>>> lst [[1, 4], [3, 9], [2, 5], [3, 2]] >>>
>>>
>>> lst.sort(cmp = lambda x,y: cmp(x[1], y[1]))
>>> lst [[3, 2], [1, 4], [2, 5], [3, 9]] >>>

works for Python 2.4
in earlier Pythons just let cmp = .. away

Regards, Daniel

what does let cmp = .. away mean?

[Shi Mu]

On 11/21/05, Daniel Schüle <uv**@rz.uni-karlsruhe.de> wrote:

Shi Mu wrote:

I have a list like [[1,4],[3,9],[2,5],[3,2]]. How can I sort the list
based on the second value in the item?
That is,
I want the list to be:
[[3,2],[1,4],[2,5],[3,9]]

>>> lst = [[1,4],[3,9],[2,5],[3,2]]
>>> lst [[1, 4], [3, 9], [2, 5], [3, 2]] >>>
>>>
>>> lst.sort(cmp = lambda x,y: cmp(x[1], y[1]))
>>> lst [[3, 2], [1, 4], [2, 5], [3, 9]] >>>

works for Python 2.4
in earlier Pythons just let cmp = .. away

Regards, Daniel

what does let cmp = .. away mean?

[Nick Craig-Wood]

Daniel Schüle <uv**@rz.uni-karlsruhe.de> wrote:

lst.sort(lambda x,y: cmp(x[1], y[1]))

Since no-one mentioned it and its a favourite of mine, you can use the
decorate-sort-undecorate method, or "Schwartzian Transform"

eg

lst = [[1,4],[3,9],[2,5],[3,2]]
# decorate - ie make a copy of each item with the key(s) first and the
# actual object last
L = [ (x[1],x) for x in lst ]
# sort
L.sort()
# undecorate
L = [ x[-1] for x in L ]

The Schwartzian transform is especially good when making the key is
expensive - it only needs to be done N times, wheras a typical sort
routine will call the cmp function N log N times. Its expensive in
terms of memory though.

With python 2.4 you can wrap it up into one line if you want

[ x[-1] for x in sorted([ (x[1],x) for x in lst ]) ]

or even

[ x[-1] for x in sorted((x[1],x) for x in lst) ]

--
Nick Craig-Wood <ni**@craig-wood.com> -- http://www.craig-wood.com/nick

[Neil Hodgson]

Nick Craig-Wood:

Since no-one mentioned it and its a favourite of mine, you can use the
decorate-sort-undecorate method, or "Schwartzian Transform"

That is what the aforementioned key argument to sort is: a built-in
decorate-sort-undecorate.

lst = [[1,4],[3,9],[2,5],[3,2]]
print lst [[1, 4], [3, 9], [2, 5], [3, 2]] lst.sort(key=lambda x: x[1])
print lst

[[3, 2], [1, 4], [2, 5], [3, 9]]

Neil

[Duncan Booth]

Neil Hodgson wrote:

Since no-one mentioned it and its a favourite of mine, you can use the
decorate-sort-undecorate method, or "Schwartzian Transform"

That is what the aforementioned key argument to sort is: a built-in
decorate-sort-undecorate.

And crucially it is a built-in DSU which gets it right more often than
naive DSU implementations.

e.g. it is stable when you reverse the order:

lst = [[4,1],[4,2],[9,3],[5,4],[2,5]]
list(reversed([ x[-1] for x in sorted([ (x[0],x) for x in lst ]) ])) [[9, 3], [5, 4], [4, 2], [4, 1], [2, 5]] l1 = list(lst)
l1.sort(key=operator.itemgetter(0), reverse=True)
l1 [[9, 3], [5, 4], [4, 1], [4, 2], [2, 5]]

and it gets incomparable objects right:
lst = [4+1j, 4+2j, 9+3j, 5+4j, 2+5j]
[ x[-1] for x in sorted([ (x.real,x) for x in lst ]) ]
Traceback (most recent call last):
File "<pyshell#39>", line 1, in -toplevel-
[ x[-1] for x in sorted([ (x.real,x) for x in lst ]) ]
TypeError: no ordering relation is defined for complex numbers l1 = list(lst)
l1.sort(key=operator.attrgetter('real'))
l1 [(2+5j), (4+1j), (4+2j), (5+4j), (9+3j)]

[bonono]

Duncan Booth wrote:

e.g. it is stable when you reverse the order:

lst = [[4,1],[4,2],[9,3],[5,4],[2,5]]
list(reversed([ x[-1] for x in sorted([ (x[0],x) for x in lst ]) ])) [[9, 3], [5, 4], [4, 2], [4, 1], [2, 5]] l1 = list(lst)
l1.sort(key=operator.itemgetter(0), reverse=True)
l1

[[9, 3], [5, 4], [4, 1], [4, 2], [2, 5]]

Just curious, which one is supposed to be the right answer ? and why
the second one is preferable over the first one(if both is right,
assume we only care about x[0]).

Of course, there is no reason to DIY when the built-in can do the job.

[Peter Otten]

bo****@gmail.com wrote:

Duncan Booth wrote:

e.g. it is stable when you reverse the order:

>>> lst = [[4,1],[4,2],[9,3],[5,4],[2,5]]
>>> list(reversed([ x[-1] for x in sorted([ (x[0],x) for x in lst ]) ]))

[[9, 3], [5, 4], [4, 2], [4, 1], [2, 5]]

>>> l1 = list(lst)
>>> l1.sort(key=operator.itemgetter(0), reverse=True)
>>> l1

[[9, 3], [5, 4], [4, 1], [4, 2], [2, 5]]

Just curious, which one is supposed to be the right answer ? and why
the second one is preferable over the first one(if both is right,
assume we only care about x[0]).

Of course, there is no reason to DIY when the built-in can do the job.

"Stability" means items with the same key preserve their relative position.
In the original list of the example [4, 1] and [4, 2] both have the same
key. Therefore [4, 1] should stay before [4, 2], so the second is the
"right" answer.

The practical advantage is that if e. g. you sort items first by color and
then by size, items of the same size will appear sorted by color. In
particular, sorting a list by the same key a second time does not change
the list.

Peter

[bonono]

Peter Otten wrote:

bo****@gmail.com wrote:

Duncan Booth wrote:

e.g. it is stable when you reverse the order:

>>> lst = [[4,1],[4,2],[9,3],[5,4],[2,5]]
>>> list(reversed([ x[-1] for x in sorted([ (x[0],x) for x in lst ]) ]))
[[9, 3], [5, 4], [4, 2], [4, 1], [2, 5]]
>>> l1 = list(lst)
>>> l1.sort(key=operator.itemgetter(0), reverse=True)
>>> l1
[[9, 3], [5, 4], [4, 1], [4, 2], [2, 5]]

Just curious, which one is supposed to be the right answer ? and why
the second one is preferable over the first one(if both is right,
assume we only care about x[0]).

Of course, there is no reason to DIY when the built-in can do the job.

"Stability" means items with the same key preserve their relative position.
In the original list of the example [4, 1] and [4, 2] both have the same
key. Therefore [4, 1] should stay before [4, 2], so the second is the
"right" answer.

The practical advantage is that if e. g. you sort items first by color and
then by size, items of the same size will appear sorted by color. In
particular, sorting a list by the same key a second time does not change
the list.

Ah, thanks. That clear things up.

[Nick Craig-Wood]

Neil Hodgson <ny*****************@gmail.com> wrote:

Nick Craig-Wood:

Since no-one mentioned it and its a favourite of mine, you can use the
decorate-sort-undecorate method, or "Schwartzian Transform"

That is what the aforementioned key argument to sort is: a built-in
decorate-sort-undecorate.

Its also python 2.4 only though :-(

(We are stuck on python 2.3 here)

--
Nick Craig-Wood <ni**@craig-wood.com> -- http://www.craig-wood.com/nick