Language: C C++ D Haskell Lua OCaml PHP Perl Plain Text Python Ruby Scheme Tcl def quick_sort_inplace(L): """Perform an in-place quicksort of the list L.""" # used for finding random numbers from random import Random rand = Random() # simple counter ops = [0,] def divide(low, high): """Divide the current list/partition into more partitions.""" if high > low: # pick a random pivot p = rand.randrange(low, high+1) # conquer this partition with that pivot p = conquer(low, high, p) # divide the conquered partition around the pivot divide(low, p-1) divide(p+1, high) def conquer(low, high, p): """Given a partition of the list, swap elements into a semi-sorted order around the pivot.""" # first, move the pivot to the end of the partition pivot = L[p] L[p], L[high] = L[high], L[p] i = low # an element to swap j = low # where we are in the list # go over the elements in this partition while low <= j < high: ops[0] = ops[0]+1 # we've found a number <= the pivot, lets swap it with itself or # the last found number greate than the pivot. j will be > than i, # and this if moves ignores numbers > than the pivot, and so i will # stop at the first number greater than the pivot, and i will stop # at the first number <= to the pivot. if L[j] <= pivot: L[i], L[j] = L[j], L[i] i = i+1 # move along in the list j = j+1 # swap the pivot out from the last position and into where the last # number greater than the pivot was found L[i], L[high] = L[high], L[i] # return the new pivot index return i # sort the list divide(0, len(L)-1) print "number of operations:", ops[0] if __name__ == "__main__": ls = [5, 8, 3, 1, 2, 99, 14, 7] print "unsorted:", ls quick_sort_inplace(ls) print "sorted:", ls Private [?] Run code