QuickSort

quicksort.py

#!/usr/bin/env python
# coding: utf-8

def quicksort(A, p=0, r=None):
    if r is None:
        r = len(A) - 1
    if p < r:
        q = partition(A, p, r)
        quicksort(A,p,q-1)
        quicksort(A,q+1,r)
    return A

def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r-1 + 1):
        if cmp(A[j], x) <= 0:
            i = i + 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i + 1

def cmp_num(a, b):
    return a - b

def cmp_pair_onlyfirst(a, b):
    return a[0] - b[0]

cmp = cmp_num
quicksort([4,3,1,2])
# [1, 2, 3, 4]

cmp = cmp_pair_onlyfirst
quicksort([(3, "first"), (2, ""), (3, "second"), (1, "")])
# [(1, ''), (2, ''), (3, 'second'), (3, 'first')]