quick sort list of tuple with python
Question: I am trying to do this in its operation algorithm quicksort to sort though the
elements of a list of tuples. Or if I have a list of this type [(0,1), (1,1),
(2,1), (3,3), (4,2), (5,1), (6,4 )] I want to sort it in function of the
second element of each tuple and obtain [(6,4), (3,3), (4,2), (0,1), (1,1),
(2,1 ), (5,1)]. I have tried using the following algorithm:

    
    
    def partition(array, begin, end, cmp):
    pivot=array[end][1]
    ii=begin
    for jj in xrange(begin, end):
      if cmp(array[jj][1], pivot):
        array[ii], array[jj] = array[jj], array[ii]
        ii+=1
    array[ii], array[end] = pivot, array[ii]
    return ii
    
    enter code hedef sort(array, cmp=lambda x, y: x > y, begin=0, end=None):
    if end is None: end = len(array)
    if begin < end:
        i = partition(array, begin, end-1, cmp)
        sort(array, cmp, i+1, end)
        sort(array, cmp, begin, i)
    

The problem is that the result is this: [4, (3, 3), (4, 2), 1, 1, 1, (5, 1)].
What do I have to change to get the correct result ??


Answer: Complex sorting patterns in Python are painless. Python's [sorting
algorithm](http://en.wikipedia.org/wiki/Timsort) is state of the art, one of
the fastest available in real-world cases. No algorithm design needed.

    
    
    >>> from operator import itemgetter
    >>> l = [(0,1), (1,1), (2,1), (3,3), (4,2), (5,1), (6,4 )]
    >>> l.sort(key=itemgetter(1), reverse=True)
    >>> l
    [(6, 4), (3, 3), (4, 2), (0, 1), (1, 1), (2, 1), (5, 1)]
    

Above,
[`itemgetter`](https://docs.python.org/3/library/operator.html#operator.itemgetter)
returns a function that returns the second element of its argument. Thus the
`key` argument to `sort` is a function that returns the item on which to sort
the list.

Python's sort is stable, so the ordering of elements with equal keys (in this
case, the second item of each tuple) is determined by the original order.

