Previous Topic

What Is Quick Sort?

Quick Sort is a fast, general-purpose sorting algorithm that works by picking a pivot, partitioning the array into elements less than (or equal to) and greater than the pivot, and then recursively sorting the partitions. It is a classic example of the divide-and-conquer paradigm.

Key Ideas

• Divide-and-conquer: Split the problem into smaller subproblems, solve them recursively, and combine (implicitly via partitioning).
• Partitioning: Rearrange elements so that all items left of the pivot are less than or equal to it, and all items right are greater.
• In-place (typically): Uses constant extra space for partitioning, with additional space from recursion.
• Average-case efficiency: Runs in O(n log n) on average, which is competitive with other efficient sorts.

Algorithm Outline

1. Choose a pivot element from the array (e.g., last, first, random, or median-of-three).
2. Partition the array around the pivot.
3. Recursively apply Quick Sort to the left and right partitions.

Pseudocode (Lomuto Partition)

function partition(A, lo, hi):
    pivot = A[hi]
    i = lo
    for j = lo to hi - 1:
        if A[j] <= pivot:
            swap A[i], A[j]
            i = i + 1
    swap A[i], A[hi]
    return i

function quick_sort(A, lo, hi):
    if lo >= hi:
        return
    p = partition(A, lo, hi)
    quick_sort(A, lo, p - 1)
    quick_sort(A, p + 1, hi)

Alternative Partition: Hoare Scheme

Hoare's partition can perform fewer swaps and is often faster, especially with many equal keys.

function partition_hoare(A, lo, hi):
    pivot = A[(lo + hi) // 2]
    i = lo - 1
    j = hi + 1
    while true:
        repeat:
            i = i + 1
        until A[i] >= pivot
        repeat:
            j = j - 1
        until A[j] <= pivot
        if i >= j:
            return j
        swap A[i], A[j]

function quick_sort_hoare(A, lo, hi):
    if lo < hi:
        p = partition_hoare(A, lo, hi)
        quick_sort_hoare(A, lo, p)
        quick_sort_hoare(A, p + 1, hi)

Complexity and Properties

• Time complexity: Best and average case O(n log n); worst case O(n^2) if partitions are highly unbalanced (e.g., poor pivot choices on already sorted data).
• Space complexity: O(log n) additional space on average due to recursion depth; worst case O(n).
• Stability: Not stable by default (equal elements may change relative order). Stable variants exist but are more complex.
• In-place: Yes (for standard implementations), which reduces memory overhead and improves cache performance.

Pivot Selection Strategies

• Last/first element: Simple but risky for already sorted or adversarial inputs.
• Random pivot: Randomizes performance, making worst cases unlikely in practice.
• Median-of-three: Choose the median of first, middle, and last elements to reduce the chance of poor partitions.

Handling Duplicates

When many elements are equal to the pivot, standard two-way partitioning can degrade. A three-way partition (Dutch National Flag) splits elements into less-than, equal-to, and greater-than partitions, improving performance with many duplicates.

Optimizations in Practice

• Switch to a simpler sort for small partitions: Many implementations switch to a small-array sort (e.g., insertion sort) for subarrays below a threshold (like 10–20 elements) to reduce overhead.
• Tail recursion elimination: Recurse into the smaller partition first and iterate on the larger one to cap recursion depth at O(log n).
• Introspective sort (introsort): Start with Quick Sort, but detect deep recursion and fall back to Heap Sort to guarantee O(n log n) worst-case time.

When to Use Quick Sort

• General-purpose in-memory sorting when stability is not required.
• Datasets that fit in CPU cache benefit from its locality.
• Scenarios where average speed and low constant factors matter.

Comparisons to Other Sorts

• Merge Sort: Predictable O(n log n) even in worst case and stable, but needs O(n) extra space (unless using complex in-place variants).
• Heap Sort: O(n log n) worst-case and in-place, but often slower in practice due to cache behavior.

Example Walkthrough

Sort [9, 3, 7, 1, 8, 2] with pivot = 2 (Lomuto):

1. Partition around 2 → [1, 2, 7, 9, 8, 3], pivot index = 1
2. Recurse left on [1] (already sorted) and right on [7, 9, 8, 3]
3. Repeat until subarrays are size 0 or 1

Common Pitfalls

• Consistently poor pivot selection (e.g., always first/last on sorted data) causing O(n^2) behavior.
• Incorrect partition boundaries leading to infinite recursion or missed elements.
• Stack overflow on worst-case recursion depth; mitigate with tail recursion elimination or iterative approach.

Applications

• Order statistics: Quickselect for finding k-th smallest/largest element.
• Top-k problems: Partial sorting by partitioning around pivots.
• Parallel and distributed variants: Partitioning enables parallel subproblem processing.

Next Topic