Language: C C++ D Haskell Lua OCaml PHP Perl Plain Text Python Ruby Scheme Tcl def quick_select(L, k): """Select the kth largest element in the list, L.""" # we need the random class to choose pivot values from random import Random rand = Random() def divide(S, k): """Choose a pivot and partition the list into three sublists using that pivot. Conquer each sublist recursively.""" length = len(S) # found it! if length < 2: print "Found by default" return S[0] # choose a pivot randomly pivot_val = S[rand.randrange(0, length)] # separate the list into 3 partitions less = [i for i in S if i < pivot_val] equal = [i for i in S if i is pivot_val] greater = [i for i in S if i > pivot_val] # the kth largest is greater than the pivot val if k <= len(greater): print k, "rd biggest in", greater return divide(greater, k) # found it! elif k <= len(greater) + len(equal): print k, "is pivot", equal return equal[0] # the kth largest is less than the pivot else: print k, "rd biggest in", less return divide(less, k - len(greater) - len(equal)) return divide(L, k) if __name__ == "__main__": ls = [5, 8, 3, 1, 2, 99, 14, 7] print quick_select(ls, 3) Private [?] Run code