Quicksort

See Wikipedia’s article on Quicksort for explanation. Following is my implementation in Python using the original partitioning scheme from the inventor of the algorithm T. Hoare.


def quicksort(data, lo, hi):
    if 0 <= lo < hi and hi >= 0:
        pivot = partition(A, lo, hi)
        quicksort(A, lo, pivot)
        quicksort(A, pivot + 1, hi)

    return data

def partition(A, lo, hi):
    print(f"Initial array: {A}")
    pivot = A[(lo + hi) // 2]  # value in the middle of the array

    i = lo                     # left index
    j = hi                     # right index

    while True:
        while A[i] < pivot:
            i += 1
        while A[j] > pivot:
            j -= 1

        if i >= j:             # we have a crossing between indices, so stop loop
            return j

        A[i], A[j] = A[j], A[i]
Complexity analysis Link to heading
  • Time: $ O(n^2) $ in the worst case scenario, and $ O(n ~ log ~ n) $ on average.


Share on:
LinkedIn