quicksort.py

import random


def partition(_list, pivot):
    '''Given a list and a pivot, returns 3 lists:
    low, [pivot], and high
    '''
    pointer = 0
    low = []
    high = []
    pivot_list = []

    for pointer in xrange(len(_list)):
        if _list[pointer] < pivot:
            low.append(_list[pointer])
        elif _list[pointer] > pivot:
            high.append(_list[pointer])
        else:
            pivot_list.append(_list[pointer])
    return low, pivot_list, high


def quicksort(_list):
    '''Takes a list, returns a sorted version of this list, using the quicksort
    algorithm
    '''
    if len(_list) <= 1:
        return _list
    pivot = random.choice(_list)
    low, pivot, high = partition(_list, pivot)
    return quicksort(low) + pivot + quicksort(high)


if __name__ == '__main__':
    print "QUICKSORT the following list"
    random_ints = [random.randint(0, 1000) for r in xrange(100)]
    print random_ints
    print "Now sorted:\n"
    print quicksort(random_ints)