randomized-quicksort.py

import random
import sys


def partition(array, lo, hi):
    pivot = random.randint(lo, hi)
    i = lo+1
    j = hi
    array[lo], array[pivot] = array[pivot], array[lo]
    while True:
        while i <= j and array[i] <= array[lo]:
            i += 1

        while j >= i and array[lo] <= array[j]:
            j -= 1

        if i >= j:
            break

        array[i], array[j] = array[j], array[i]

    array[lo], array[j] = array[j], array[lo]
    return j

def do_rand_quicksort(array, lo, hi):
    if lo >= hi:
        return
    # pick a pivot
    pos = partition(array, lo, hi)
    do_rand_quicksort(array, lo, pos-1)
    do_rand_quicksort(array, pos+1, hi)


def rand_quicksort(array):
    if len(array) <= 1:
        return array
    do_rand_quicksort(array, 0, len(array)-1)

if __name__ == '__main__':
    array = map(int, sys.argv[1:])
    print array
    rand_quicksort(array)
    print array