Quick Sort¶
Definition¶
A divide-and-conquer sorting algorithm that selects a 'pivot' element and partitions the array around it, placing smaller elements left and larger elements right.
Key Insight: After partitioning, pivot is in its FINAL sorted position.
Big O Complexity¶
When to Use¶
Pros and Cons¶
Implementation¶
Lomuto Partition (Simple)¶
public void quickSort(int[] arr) {
quickSort(arr, 0, arr.length - 1);
}
private void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
// Lomuto partition - pivot is last element
private int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1; // Boundary of elements < pivot
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high); // Place pivot in correct position
return i + 1;
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
Hoare Partition (Efficient)¶
// Hoare partition - fewer swaps on average
private int partitionHoare(int[] arr, int low, int high) {
int pivot = arr[low + (high - low) / 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, j);
}
}
// Quick sort using Hoare
private void quickSortHoare(int[] arr, int low, int high) {
if (low < high) {
int p = partitionHoare(arr, low, high);
quickSortHoare(arr, low, p); // Note: includes p
quickSortHoare(arr, p + 1, high);
}
}
Randomized Quick Sort¶
private Random random = new Random();
private int partitionRandomized(int[] arr, int low, int high) {
// Random pivot selection
int randomIndex = low + random.nextInt(high - low + 1);
swap(arr, randomIndex, high);
return partition(arr, low, high); // Standard Lomuto
}
Median-of-Three Pivot¶
private int medianOfThree(int[] arr, int low, int high) {
int mid = low + (high - low) / 2;
// Sort low, mid, high
if (arr[low] > arr[mid]) swap(arr, low, mid);
if (arr[low] > arr[high]) swap(arr, low, high);
if (arr[mid] > arr[high]) swap(arr, mid, high);
// Place median at high-1
swap(arr, mid, high - 1);
return arr[high - 1]; // Return pivot value
}
3-Way Quick Sort (Dutch National Flag)¶
// Efficient for arrays with many duplicates
private void quickSort3Way(int[] arr, int low, int high) {
if (low >= high) return;
int lt = low; // arr[low..lt-1] < pivot
int gt = high; // arr[gt+1..high] > pivot
int i = low + 1; // arr[lt..i-1] == pivot
int pivot = arr[low];
while (i <= gt) {
if (arr[i] < pivot) {
swap(arr, lt++, i++);
} else if (arr[i] > pivot) {
swap(arr, i, gt--);
} else {
i++;
}
}
// arr[low..lt-1] < pivot = arr[lt..gt] < arr[gt+1..high]
quickSort3Way(arr, low, lt - 1);
quickSort3Way(arr, gt + 1, high);
}
Iterative Quick Sort (No Recursion)¶
public void quickSortIterative(int[] arr) {
Stack<int[]> stack = new Stack<>();
stack.push(new int[]{0, arr.length - 1});
while (!stack.isEmpty()) {
int[] range = stack.pop();
int low = range[0];
int high = range[1];
if (low < high) {
int pivotIndex = partition(arr, low, high);
// Push larger subarray first (tail call optimization)
if (pivotIndex - low > high - pivotIndex) {
stack.push(new int[]{low, pivotIndex - 1});
stack.push(new int[]{pivotIndex + 1, high});
} else {
stack.push(new int[]{pivotIndex + 1, high});
stack.push(new int[]{low, pivotIndex - 1});
}
}
}
}
Tail-Recursive Optimization¶
// Reduces stack space by iterating on larger half
private void quickSortTailOptimized(int[] arr, int low, int high) {
while (low < high) {
int pivotIndex = partition(arr, low, high);
// Recurse on smaller half, iterate on larger
if (pivotIndex - low < high - pivotIndex) {
quickSortTailOptimized(arr, low, pivotIndex - 1);
low = pivotIndex + 1;
} else {
quickSortTailOptimized(arr, pivotIndex + 1, high);
high = pivotIndex - 1;
}
}
}
Quick Select (K-th Smallest)¶
// Find k-th smallest element in O(n) average time
public int quickSelect(int[] arr, int k) {
return quickSelect(arr, 0, arr.length - 1, k - 1);
}
private int quickSelect(int[] arr, int low, int high, int k) {
if (low == high) return arr[low];
int pivotIndex = partitionRandomized(arr, low, high);
if (k == pivotIndex) {
return arr[k];
} else if (k < pivotIndex) {
return quickSelect(arr, low, pivotIndex - 1, k);
} else {
return quickSelect(arr, pivotIndex + 1, high, k);
}
}
Hybrid: Introsort¶
// Switches to heapsort when recursion too deep
public void introSort(int[] arr) {
int maxDepth = (int) (2 * Math.log(arr.length) / Math.log(2));
introSort(arr, 0, arr.length - 1, maxDepth);
}
private void introSort(int[] arr, int low, int high, int depthLimit) {
int size = high - low + 1;
if (size < 16) {
// Use insertion sort for small arrays
insertionSort(arr, low, high);
return;
}
if (depthLimit == 0) {
// Switch to heapsort
heapSort(arr, low, high);
return;
}
int pivot = partition(arr, low, high);
introSort(arr, low, pivot - 1, depthLimit - 1);
introSort(arr, pivot + 1, high, depthLimit - 1);
}
Step-by-Step Example¶
Dual-Pivot Quick Sort¶
// Java 7+ uses dual-pivot for primitives
private void dualPivotQuickSort(int[] arr, int low, int high) {
if (low >= high) return;
// Choose two pivots
if (arr[low] > arr[high]) swap(arr, low, high);
int pivot1 = arr[low];
int pivot2 = arr[high];
int lt = low + 1; // arr[low+1..lt-1] < pivot1
int gt = high - 1; // arr[gt+1..high-1] > pivot2
int i = lt; // arr[lt..i-1] in [pivot1, pivot2]
while (i <= gt) {
if (arr[i] < pivot1) {
swap(arr, i++, lt++);
} else if (arr[i] > pivot2) {
swap(arr, i, gt--);
} else {
i++;
}
}
// Place pivots
swap(arr, low, --lt);
swap(arr, high, ++gt);
// Recurse on three parts
dualPivotQuickSort(arr, low, lt - 1);
dualPivotQuickSort(arr, lt + 1, gt - 1);
dualPivotQuickSort(arr, gt + 1, high);
}
Tips & Tricks¶
