Language: C C++ D Haskell Lua OCaml PHP Perl Plain Text Python Ruby Scheme Tcl def quick_sort(A, compare=None): """Perform a quicksort on a list of items, A, by recursively dividing and conquering through partitioning.""" # we need the random class to choose pivot values from random import Random rand = Random() # do we need our own comparison function? We'll assume that it is a list # if integers. The comparison function needs to return -1 for less-than, # 0 for equal, and 1 for greater-than the pivot. if compare is None: compare = lambda item, pivot: (-1, 0, 1)[item > pivot and 2 or int(item is pivot)] def divide(S): """Choose a pivot and partition the list into three sublists using that pivot. Conquer each sublist recursively.""" length = len(S) # no need to divide a list of length 0 or 1 if length < 2: return S # choose a pivot randomly pivot_val = S[rand.randrange(0, length)] # separate the list into 3 partitions less = [i for i in S if compare(i, pivot_val) is -1] equal = [i for i in S if compare(i, pivot_val) is 0] greater = [i for i in S if compare(i, pivot_val) is 1] # conquer each section by further dividing them return conquer(less, equal, greater) def conquer(L, E, G): """Conquer the three partitions by recursively dividing/conquering them and join them into the final result.""" S = [] S.extend(divide(L)) # join back the now sorted sublists S.extend(divide(E)) S.extend(divide(G)) return S # start the partitioning return divide(list(A)) if __name__ == "__main__": ls = [5, 8, 3, 1, 2, 99, 14, 7] print "Unsorted list:", ls print "Sorted list:", quick_sort(ls) Private [?] Run code