The Principle of Quick Sort

Quick sort adopts the divide and conquer strategy. Its basic idea is:

Choose a Pivot: Select an element from the array as the pivot.
Partition: Rearrange the array so that elements smaller than the pivot are placed before it, and elements larger than the pivot are placed after it.
Recursive Sorting: Recursively apply quick sort to the subarrays before and after the pivot.

Basic Implementations

1. Lomuto Partition Scheme

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];  // Choose the last element as pivot
    int i = low;            // Boundary for elements smaller than pivot
    
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            swap(arr[i], arr[j]);
            i++;
        }
    }
    swap(arr[i], arr[high]);
    return i;
}
 
void quickSort(vector<int>& arr, int low, int high) {
    }
}

2. Hoare Partition Scheme

int partitionHoare(vector<int>& arr, int low, int high) {
    int pivot = arr[(low + high) / 2];
    int i = low - 1;
    int j = high + 1;
    
    while (true) {
        do { i++; } while (arr[i] < pivot);
        do { j--; } while (arr[j] > pivot);
        
        if (i >= j) return j;
        
        swap(arr[i], arr[j]);
    }
}
 
void quickSortHoare(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partitionHoare(arr, low, high);
        quickSortHoare(arr, low, pi);
        quickSortHoare(arr, pi + 1, high);
    }
}

Comparison of Partition Schemes

Feature	Lomuto Partition	Hoare Partition
Implementation Complexity	Simpler	More complex
Number of Swaps	More	Fewer
Pivot Selection	Usually last element	Usually middle element
Recursive Calls	Pivot not in subarrays	Pivot may be in subarrays
Efficiency	Average	Usually faster

Optimization Strategies

1. Randomized Quick Sort

int partitionRandom(vector<int>& arr, int low, int high) {
    srand(time(NULL));
    int random = low + rand() % (high - low);
    swap(arr[random], arr[high]);
    return partition(arr, low, high);
}

2. Median-of-Three Method

int medianOfThree(vector<int>& arr, int low, int high) {
    int mid = low + (high - low) / 2;
    
    // Ensure arr[low] <= arr[mid] <= arr[high]
    if (arr[low] > arr[mid]) swap(arr[low], arr[mid]);
    if (arr[low] > arr[high]) swap(arr[low], arr[high]);
    if (arr[mid] > arr[high]) swap(arr[mid], arr[high]);
    
    return mid;
}

3. Small Array Optimization

void insertionSort(vector<int>& arr, int low, int high) {
    for (int i = low + 1; i <= high; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= low && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}
 
void optimizedQuickSort(vector<int>& arr, int low, int high) {
    if (high - low < 16) {  // Threshold can be adjusted
        insertionSort(arr, low, high);
        return;
    }
    
    int pi = partition(arr, low, high);
    optimizedQuickSort(arr, low, pi - 1);
    optimizedQuickSort(arr, pi + 1, high);
}

4. Three-Way Partitioning (for handling duplicates)

void quickSort3Way(vector<int>& arr, int low, int high) {
    if (high <= low) return;
    
    int lt = low, gt = high;
    int pivot = arr[low];
    int i = low;
    
    while (i <= gt) {
        if (arr[i] < pivot) {
            swap(arr[lt++], arr[i++]);
        } else if (arr[i] > pivot) {
            swap(arr[i], arr[gt--]);
        } else {
            i++;
        }
    }
    
    quickSort3Way(arr, low, lt - 1);
    quickSort3Way(arr, gt + 1, high);
}

Algorithm Analysis

Time Complexity

Scenario	Time Complexity
Best Case	O(n log n)
Average Case	O(n log n)
Worst Case	O(n²)

Worst case occurs when partitioning is highly unbalanced (e.g., sorted arrays).

Space Complexity

Scenario	Space Complexity
Best/Average	O(log n)
Worst Case	O(n)

Space is consumed by the recursive call stack.

Stability

Quick sort is unstable because the relative order of equal elements may change during partitioning.

Practical Applications

C++ Standard Library: std::sort() often uses an optimized version (e.g., Introsort).
Large Data Sorting: Preferred for sorting large-scale datasets.
Embedded Systems: More popular than merge sort in memory-constrained environments.

Common Questions

Q1: Why is quick sort faster than merge sort?

Both have O(n log n) complexity, but quick sort has smaller constant factors and is in-place (no extra space needed).

Q2: How to avoid the worst case?

Use randomized pivot selection.
Adopt the median-of-three method.
Switch to heap sort for excessive recursion depth (Introsort).

Q3: When is quick sort unsuitable?

When stable sorting is required.
With very limited memory (risk of stack overflow from recursion).
For nearly sorted data (insertion sort may perform better).

Summary

Quick sort is one of the most widely used sorting algorithms due to its excellent average performance. Optimizations like smart pivot selection, improved partitioning, and handling edge cases can significantly boost its efficiency. Understanding quick sort helps in writing efficient code and mastering the divide-and-conquer paradigm.