Beginner LevelData Structures & Algorithms
How does Quick Sort work and what makes it fast in practice?
ā Interview Prompt: Explain Quick Sort, pivot selection, partitioning (Lomuto vs Hoare), O(N log N) average vs O(NĀ²) worst-case, and when to use it.
Quick Sort is a divide-and-conquer algorithm:
1
Choose a pivot (e.g., last element, median-of-3).
2
Partition: Rearrange array so elements < pivot are left, elements > pivot are right.
3
Recursively sort left and right partitions.
Complexity:
ā¢
Average: $O(N \log N)$ (random or median pivot).
ā¢
Worst: $O(N^2)$ (sorted input with last-element pivot ā always smallest partition).
ā¢
Space: $O(\log N)$ call stack average, $O(N)$ worst.
Why Faster in Practice:
ā¢
Excellent cache locality (in-place partitioning).
ā¢
Small constant factors vs Merge Sort's $O(N)$ auxiliary allocation.
ā¢
Randomised pivot eliminates worst case for most inputs.
Code Implementation Example
typescript
// Quick Sort with Lomuto partition scheme
function quickSort(arr: number[], lo = 0, hi = arr.length - 1): void {
if (lo >= hi) return;
const p = partition(arr, lo, hi);
quickSort(arr, lo, p - 1);
quickSort(arr, p + 1, hi);
}
function partition(arr: number[], lo: number, hi: number): number {
const pivot = arr[hi];
let i = lo - 1;
for (let j = lo; j < hi; j++) {
if (arr[j] <= pivot) [arr[++i], arr[j]] = [arr[j], arr[i]];
}
[arr[++i], arr[hi]] = [arr[hi], arr[i]];
return i;
}š”Quick Sort with Lomuto partition ā O(N log N) average in-place.
šÆ Interview Key Takeaway
Quick Sort is the fastest practical sort due to cache efficiency. Use randomised pivot or median-of-3 to avoid O(NĀ²) worst case.
#DSA#Quick Sort#Sorting#Divide and Conquer#Beginner
Back to all Data Structures & Algorithms Questionsā