1

I was working on a geometry project in python and I came across an intriguing problem. Assume I have a list of Cartesian coordinates like this:

[[1, 0], [3, 0], [2, 1], [3.5, 2], [4, 3], [6, 1], [6.5, 0], [10, 2], [10, 5], [9, 3.5], [7, 3], [9, 7], [7, 8], [5, 7], [4, 5], [2, 8], [1, 7], [0, 5], [1, 3], [0, 2]]

What would be the best way to sort this list by descending y-value THEN increasing x-value if two coordinates exist with the same y-value? The output should be:

[[2, 8], [7, 8], [1, 7], [5, 7], [9, 7], [0, 5], [4, 5], [10, 5], [9, 3.5], [1, 3], [4, 3], [7, 3], [0, 2], [3.5, 2], [10, 2], [2, 1], [6, 1], [1, 0], [3, 0], [6.5, 0]]

user3002473
  • 4,835
  • 8
  • 35
  • 61

3 Answers3

4

You can supply a key function to list.sort to determine what value each item in your list should be mapped to for sorting. In your case, you can use a tuple of the negative Y-coordinate, and the X-coordinate to get your desired result:

>>> coordinates = [[1, 0], [3, 0], [2, 1], [3.5, 2], [4, 3], [6, 1], [6.5, 0], [10, 2], [10, 5], [9, 3.5], [7, 3], [9, 7], [7, 8], [5, 7], [4, 5], [2, 8], [1, 7], [0, 5], [1, 3], [0, 2]]
>>> coordinates.sort(key=lambda x: (-x[1], x[0]))
>>> coordinates
[[2, 8], [7, 8], [1, 7], [5, 7], [9, 7], [0, 5], [4, 5], [10, 5], [9, 3.5], [1, 3], [4, 3], [7, 3], [0, 2], [3.5, 2], [10, 2], [2, 1], [6, 1], [1, 0], [3, 0], [6.5, 0]]
poke
  • 369,085
  • 72
  • 557
  • 602
2

Poke's answer is the right answer in most cases.

Just in case you are doing this on Python prior to Python 2.4 or if the comparison function is really expensive, you can use Decorate-Sort-Undecorate (DSU or the Schwartzian transform) 

>>> coord = [[1, 0], [3, 0], [2, 1], [3.5, 2], [4, 3], [6, 1], [6.5, 0], [10, 2], [10, 5], [
9, 3.5], [7, 3], [9, 7], [7, 8], [5, 7], [4, 5], [2, 8], [1, 7], [0, 5], [1, 3], [0, 2]]
>>> decorated=[[(-y,x),x,y] for x,y in coord]
>>> [[x,y] for t,x,y in sorted(decorated)]
[[2, 8], [7, 8], [1, 7], [5, 7], [9, 7], [0, 5], [4, 5], [10, 5], [9, 3.5], [1, 3], [4, 3], [7, 3], [0, 2], [3.5, 2], [10, 2], [2, 1], [6, 1], [1, 0], [3, 0], [6.5, 0]]

Or:

>>> [[x,y] for t,x,y in sorted([[(-y,x),x,y] for x,y in coord])]
[[2, 8], [7, 8], [1, 7], [5, 7], [9, 7], [0, 5], [4, 5], [10, 5], [9, 3.5], [1, 3], [4, 3], [7, 3], [0, 2], [3.5, 2], [10, 2], [2, 1], [6, 1], [1, 0], [3, 0], [6.5, 0]]

These techniques (and more) are in the Python sorting HowTo

dawg
  • 98,345
  • 23
  • 131
  • 206
  • *“Python prior to Python 2.4”* – I just hope that’s nowhere the case… – poke Mar 16 '14 at 20:27
  • 1
    +1 for the tencity of presenting a pre-python 2.4 solution =) – alvas Mar 16 '14 at 20:29
  • Huh, I've never heard of DSU sorting, thats a neat little method! Thanks for sharing! – user3002473 Mar 16 '14 at 20:32
  • @poke: Lots of people don't update their Python for 10, 11 years! ;-) – dawg Mar 16 '14 at 20:34
  • Support for Python 2.4 ended in 2008 though, so I’m not sure why I should give them support for their problems if they still use it :P – poke Mar 16 '14 at 20:36
  • 1
    Mostly I just think it is a useful method for languages that do NOT have key functions (Perl, Lisp, etc) – dawg Mar 16 '14 at 20:40
0

Using sorted and specifying the sorting criterion with a lambda function using a tuple:

>>> coord = [[1, 0], [3, 0], [2, 1], [3.5, 2], [4, 3], [6, 1], [6.5, 0], [10, 2], [10, 5], [9, 3.5], [7, 3], [9, 7], [7, 8], [5, 7], [4, 5], [2, 8], [1, 7], [0, 5], [1, 3], [0, 2]]
>>> sorted(coord, key=lambda x: (-x[1], x[0]))
[[2, 8], [7, 8], [1, 7], [5, 7], [9, 7], [0, 5], [4, 5], [10, 5], [9, 3.5], [1, 3], [4, 3], [7, 3], [0, 2], [3.5, 2], [10, 2], [2, 1], [6, 1], [1, 0], [3, 0], [6.5, 0]]

The order in the lambda function tuple defines the order by which the criterion are considered.

x[1] : sort by second element in ascending order

-x[1] : sort by second element in descending order

x[0] : sort by first element in ascending order

Community
  • 1
  • 1
alvas
  • 115,346
  • 109
  • 446
  • 738