quicksort.py

import random


def quicksort(array, a=None, b=None):
    a = a if a is not None else 0
    b = b if b is not None else len(array) - 1

    #pivot = array[a + (b - a) / 2]
    pivot = array[random.randint(a, b)]

    left = a
    right = b
    while left <= right:
        while array[left] < pivot:
            left += 1

        while array[right] > pivot:
            right -= 1

        if left <= right:
            tmp = array[left]
            array[left] = array[right]
            array[right] = tmp

            left += 1
            right -= 1

    if right > a:
        quicksort(array, a, right)

    if left < b:
        quicksort(array, left, b)


for _ in xrange(25):
    A = [random.randint(0, 100) for _ in xrange(50)]
    sA = sorted(A)
    quicksort(A)
    print A, sA == A