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)