quicksort.py

# generate random integer values
from random import randint


def swap(arr, x, y):
    temp = arr[x]
    arr[x] = arr[y]
    arr[y] = temp


def partition(arr, left, right):
    pivot = arr[left]
    low = left + 1
    high = right - 1

    while low <= high:
        while low <= high and arr[low] <= pivot:
            low += 1
        while high >= low and arr[high] >= pivot:
            high -= 1
        if low < high:
            swap(arr, low, high)
    swap(arr, left, high)

    return high


def quick_sort(arr, left, right):
    if left < right - 1:
        q = partition(arr, left, right)
        quick_sort(arr, left, q)
        quick_sort(arr, q + 1, right)
    return arr


def qs(arr):
    arr2 = arr[:]
    quick_sort(arr, 0, len(arr))
    arr2.sort()
    assert arr2 == arr
    return arr


for i in range(1, 1000):
    print(qs([randint(1, 200) for ii in range(0, 1000)]))