Overview
Quick Sort chooses a pivot, partitions elements into less/greater, then recursively sorts the partitions.
Analogy
Pivot guest at a doorway: shorter to the left, taller to the right, then repeat inside each room.
Step-by-step
- Choose a pivot (middle or random).
- Partition so items < pivot go left, > pivot go right (equals can sit with pivot).
- Recursively quicksort left and right partitions.
- Combine; array is sorted in place.
- Stop when partition size ≤ 1.
Visual
Partition [9,3,7,1] around pivot 7 → [3,1 | 7 | 9].
Common mistakes
- Always picking first/last as pivot, causing O(n²) on sorted input.
- Partition loop that fails to move pointers → infinite loop.
- Not handling many duplicates (use 3-way partition).
Practice questions
- Implement Lomuto vs Hoare partition and compare swaps.
- Add random pivot; test on sorted and reverse-sorted arrays.
- Trace quicksort with duplicates; explain stability (it is unstable).
Time
Average O(n log n); worst O(n²) if partitions are skewed
Space
O(log n) recursion stack on average
AI Wisdom