Topic 51 of 78
Quick Sort
Overview
Quick Sort is another 'Divide and Conquer' algorithm, but it takes a different approach. It picks a 'Pivot' element and partitions the array so that everything smaller than the pivot is on the left, and everything larger is on the right. It then recursively does this for the left and right sides. In practice, it is often the fastest sorting algorithm due to excellent CPU cache locality and O(1) space complexity, despite having a worst-case time complexity of O(N^2).
Syntax
By avoiding the creation of temporary arrays, Quick Sort operates entirely in-place (O(1) extra space).
The Quick Sort Algorithm
java
public void quickSort(int[] arr, int low, int high) {
if (low < high) {
// pi is partitioning index, arr[pi] is now at right place
int pi = partition(arr, low, high);
// Recursively sort elements before and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
public int partition(int[] arr, int low, int high) {
int pivot = arr[high]; // Choosing the last element as pivot
int i = (low - 1); // Index of smaller element
for (int j = low; j < high; j++) {
// If current element is smaller than the pivot
if (arr[j] < pivot) {
i++;
// Swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}Common Pitfalls
- Picking a bad pivot strategy (like always picking the last element) on an already sorted array causes O(N^2) performance degradation.
- Implementing the partition logic incorrectly, leading to infinite recursion or out-of-bounds exceptions.
Interview Tips
- Quick Sort operates In-Place (O(1) Space), making it highly memory efficient compared to Merge Sort.
Real-World Example
Java's `Arrays.sort(int[])` uses a highly optimized Dual-Pivot Quicksort because primitive numbers don't require stability and Quicksort is incredibly fast in-memory.
example
java
int[] numbers = {5, 2, 9, 1, 5, 6};
// This executes an extremely fast Quicksort under the hood
Arrays.sort(numbers);