quicksort.py

import random
generate = lambda length=10, min=0, max=100 : [random.randint(min, max) for _ in range(length)]

def partition(array, start, end):
    def swap(x, y):
        array[x], array[y] = array[y], array[x]

    pivotIndex = start
    pivotValue = array[end]
    for i in range(start, end + 1):
        if array[i] < pivotValue:
            swap(i, pivotIndex)
            pivotIndex += 1
    swap(pivotIndex, end)
    return pivotIndex

def quicksort(array, start, end):
    if start >= end:
        return
    index = partition(array, start, end)
    quicksort(array, start, index - 1)
    quicksort(array, index + 1, end)

def verify(array):
    prev = array[0]
    for val in array:
        if val < prev:
            return False
        prev = val
    return True

for _ in range(1000):
    array = generate()
    # print(array)
    quicksort(array, 0, len(array)-1)
    # print(array)
    if not verify(array):
        print('Failed')