Algorithm Overview

Quick Sort, often referred to as Hoare Sort, operates on a divide-and-conquer principle similar to the pre-order traversal of a binary tree. The core objective is to place a selected pivot element into its final sorted position while ensuring all elements to its left are smaller and all elements to its right are larger. This process repeats recursively for the sub-arrays on either side of the pivot.

The algorithm exhibits an average time complexity of O(N log N) and a space complexity of O(log N) due to the recursive stack frames. However, it is an unstable sorting algorithm; the relative order of equal elements may change during partitioning. Furthermore, without optimization, Quick Sort degrades to O(N²) time complexity when processing already sorted or near-sorted data.

Pivot Selection: Median-of-Three

To mitigate the risk of worst-case performance on ordered data, the pivot selection strategy is crucial. A common optimization is the Median-of-Three method. This involves selecting the median value among the first, middle, and last elements of the current array segment. Swapping this median value to the beginning of the array ensures a balanced partition, preventing the deep recursion trees associated with already sorted inputs.

int GetMedianIndex(int* data, int low, int high) {
    int mid = low + (high - low) / 2;
    
    if (data[low] > data[high]) {
        if (data[mid] > data[low]) {
            return low;
        } else if (data[mid] < data[high]) {
            return high;
        } else {
            return mid;
        }
    } else { // data[low] <= data[high]
        if (data[mid] < data[low]) {
            return low;
        } else if (data[mid] > data[high]) {
            return high;
        } else {
            return mid;
        }
    }
}

Partitioning Methods

The partitioning step divides the array into two parts. Several implementations exist to achieve this, notably the Hoare method, the Digging (or Pit) method, and the Double Pointer method.

Hoare Method

The original approach uses two pointers starting from opposite ends. If the pivot is at the leftmost index (low), the right pointer must move first. The right pointer searches for an element smaller than the pivot, while the left pointer searches for an element larger. Once found, they are swapped. The cycle repeats until the pointers meet. The pivot is then swapped into the meeting position.

Why right moves first: If the left pointer moves first in an ascending sort, it might stop on a value larger than the pivot. If it reaches the right boundary (which hasn't moved yet), swapping the pivot there would place a large value to the left of the pivot, breaking the invariant. Moving right first guarantees that the meeting position holds a value smaller than or equal to the pivot (or the pivot itself).

int PartitionHoare(int* data, int low, int high) {
    int medianIdx = GetMedianIndex(data, low, high);
    std::swap(data[low], data[medianIdx]);
    
    int pivotIdx = low;
    int left = low;
    int right = high;
    
    while (left < right) {
        // Right searches for value < pivot
        while (left < right && data[right] >= data[pivotIdx]) {
            right--;
        }
        // Left searches for value > pivot
        while (left < right && data[left] <= data[pivotIdx]) {
            left++;
        }
        std::swap(data[left], data[right]);
    }
    std::swap(data[pivotIdx], data[left]);
    return left;
}

Digging (Pit) Method

This variation visualizes the pivot's position as an empty 'pit'. The pivot value is saved, and the leftmost position is marked as the first pit. The right pointer moves left to find a value smaller than the pivot; once found, it fills the current pit, creating a new pit at the right pointer's location. The left pointer then moves right to find a value larger than the pivot to fill the new pit. This continues until the pointers meet, at which point the saved pivot value is placed into the final pit.

int PartitionDigging(int* data, int low, int high) {
    int medianIdx = GetMedianIndex(data, low, high);
    std::swap(data[low], data[medianIdx]);
    
    int pivotVal = data[low];
    int hole = low;
    
    while (low < high) {
        while (low < high && data[high] >= pivotVal) {
            high--;
        }
        data[hole] = data[high];
        hole = high;
        
        while (low < high && data[low] <= pivotVal) {
            low++;
        }
        data[hole] = data[low];
        hole = low;
    }
    data[hole] = pivotVal;
    return hole;
}

Double Pointer (Lomuto) Method

This method uses two pointers, prev and curr, both starting near the beginning. prev tracks the boundary of elements smaller than the pivot. curr scans the array. If curr finds an element smaller than the pivot, prev is incremented and swapped with curr. This effectively pushes larger elements to the right. After the scan, the pivot is swapped with prev.

int PartitionDoublePointer(int* data, int low, int high) {
    int medianIdx = GetMedianIndex(data, low, high);
    std::swap(data[low], data[medianIdx]);
    
    int pivotVal = data[low];
    int prev = low;
    
    for (int curr = low + 1; curr <= high; ++curr) {
        if (data[curr] < pivotVal) {
            prev++;
            std::swap(data[prev], data[curr]);
        }
    }
    std::swap(data[low], data[prev]);
    return prev;
}

Optimization for Small Intervals

Recursive calls are expensive for small arrays. A common optimization is to switch to Insertion Sort when the sub-array size falls below a certain threshold (e.g., 10 elements). This reduces the overhead of function calls and stack depth, particularly for the 'leaf nodes' of the recursion tree.

Non-Recursive Implementation

Deep recursion can lead to stack overflow. An iterative implementation uses an explicit stack to manage the indices. The algorithm pushes the bounds of the current sub-array onto the stack, loops to pop and partition, and pushes the bounds of the resulting sub-arrays until the stack is empty.

void QuickSortIterative(int* data, int low, int high) {
    std::stack> bounds;
    bounds.push({low, high});
    
    while (!bounds.empty()) {
        auto [currentLow, currentHigh] = bounds.top();
        bounds.pop();
        
        if (currentLow >= currentHigh) continue;
        
        int pivot = PartitionDoublePointer(data, currentLow, currentHigh);
        
        // Push right sub-array first
        if (pivot + 1 < currentHigh) {
            bounds.push({pivot + 1, currentHigh});
        }
        // Push left sub-array
        if (currentLow < pivot - 1) {
            bounds.push({currentLow, pivot - 1});
        }
    }
}