python quicksort

quicksort.py

import copy
import random
import time
import typing


def lomuto_quicksort(arr: typing.List[int]):
    if len(arr) <= 1:
        return

    def _quicksort(arr: typing.List[int], start: int, end: int):
        if end - start <= 1:
            return

        mid = arr[start]
        new_part_idx = start

        for i in range(start + 1, end):
            if arr[i] < mid:
                new_part_idx += 1
                arr[i], arr[new_part_idx] = arr[new_part_idx], arr[i]

        arr[start], arr[new_part_idx] = arr[new_part_idx], arr[start]

        _quicksort(arr, start, new_part_idx + 1)
        _quicksort(arr, new_part_idx + 1, end)

    _quicksort(arr, 0, len(arr))


def hoare_quicksort(arr: typing.List[int]):
    if len(arr) <= 1:
        return

    def _quicksort(arr: typing.List[int], start: int, end: int):
        if end - start <= 1:
            return

        mid = arr[(start + (end - 1)) // 2]

        left_idx = start
        right_idx = end - 1

        while True:
            while arr[left_idx] < mid:
                left_idx += 1
            while arr[right_idx] > mid:
                right_idx -= 1

            if left_idx >= right_idx:
                break

            arr[left_idx], arr[right_idx] = arr[right_idx], arr[left_idx]
            left_idx += 1
            right_idx -= 1

        _quicksort(arr, start, right_idx + 1)
        _quicksort(arr, right_idx + 1, end)

    _quicksort(arr, 0, len(arr))


def lomuto_quicksort_worklist(arr: typing.List[int]):
    if len(arr) <= 1:
        return

    worklist = [(0, len(arr))]

    while len(worklist) > 0:
        start, end = worklist.pop()

        mid = arr[start]
        new_part_idx = start

        for i in range(start + 1, end):
            if arr[i] < mid:
                new_part_idx += 1
                arr[i], arr[new_part_idx] = arr[new_part_idx], arr[i]

        arr[start], arr[new_part_idx] = arr[new_part_idx], arr[start]

        tmp = new_part_idx + 1
        if tmp - start > 1:
            worklist.append((start, tmp))

        if end - tmp > 1:
            worklist.append((tmp, end))


def hoare_quicksort_worklist(arr: typing.List[int]):
    if len(arr) <= 1:
        return

    worklist = [(0, len(arr))]

    while len(worklist) > 0:
        start, end = worklist.pop()

        mid = arr[(start + (end - 1)) // 2]

        left_idx = start
        right_idx = end - 1

        while True:
            while arr[left_idx] < mid:
                left_idx += 1
            while arr[right_idx] > mid:
                right_idx -= 1

            if left_idx >= right_idx:
                break

            arr[left_idx], arr[right_idx] = arr[right_idx], arr[left_idx]
            left_idx += 1
            right_idx -= 1

        tmp = right_idx + 1
        if tmp - start > 1:
            worklist.append((start, tmp))

        if end - tmp > 1:
            worklist.append((tmp, end))


def benchmark(algo: typing.Callable[[typing.List[int]], None],
              testcase=typing.List[typing.List[int]],
              verify=False):
    start_time = time.time()

    for case in testcase:
        if verify:
            print(case)

        algo(case)

        if verify:
            print(case)
            assert case == sorted(case)

    end_time = time.time()
    return end_time - start_time


testcase = [[random.randint(-256, 256) for _ in range(256)]
            for _ in range(25565)]

print(f'{benchmark(lomuto_quicksort, copy.deepcopy(testcase)) = }')
print(f'{benchmark(lomuto_quicksort_worklist, copy.deepcopy(testcase)) = }')
print(f'{benchmark(hoare_quicksort, copy.deepcopy(testcase)) = }')
print(f'{benchmark(hoare_quicksort_worklist, copy.deepcopy(testcase)) = }')