QuickSort

Tldr

Quicksort is a divide-and-conquer algorithm for sorting arrays.

1. Pick a pivot element from the array
2. Partition the array into two parts
3. Elements $\le$ pivot, go to the left
4. Elements $>$ pivot, go to the right
5. Recursively sort the two parts
6. Concatenate: sorted(left) + [pivot] + sorted(right)

QUICKSORT(A, p, r):
    if p < r:
        q = PARTITION(A, p, r)
        QUICKSORT(A, p, q - 1)
        QUICKSORT(A, q + 1, r)

PARTITION(A, p, r):
    x = A[r]                 // pivot
    i = p - 1
    for j = p to r - 1:
        if A[j] <= x:
            i = i + 1
            exchange A[i] <-> A[j]
    exchange A[i + 1] <-> A[r]
    return i + 1             // pivot index after partition

Python implementation:

def partition(A, p, r):
    pivot = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= pivot:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1
 
 
def quicksort(A, p=0, r=None):
    if r is None:
        r = len(A) - 1
    if p < r:
        q = partition(A, p, r)
        quicksort(A, p, q - 1)
        quicksort(A, q + 1, r)
 

Time complexity analysis:

Basic analysis:

• Let $T(n)$ be the running time on $n$ elements.
• Each partition step scans the array once $\Rightarrow \Theta (n)$ time.
• Let the pivot split the array into sizes $k$ and $n-k-1$.
  • $T(n)=T(k)+T(n-k-1)+\Theta (n)$
  • Best case: the pivot splits evenly (n/2 on each side):
    • $T(n)=2T(n/2)+\Theta (n)\Rightarrow \text{by the master theorem},T(n)=\Theta (n\text{logn})$
  • Average Case
  • Worst Case

Randomized QuickSort