Overview
Quick sort ek pivot select karta hai, chhote ko left aur bade ko right rakhta hai, recursively sort karta hai.
Analogy
Teacher ne class ko kisi ki height ke hisaab se do groups mein bata diya, phir har group sort karo.
Step-by-step
- Base case: n<=1 toh return
- Pivot choose karo (last/random/median)
- Less than/equal/greater than teen parts mein batao
- Less than aur greater than parts recursively sort karo
Visual
[3,6,8,10,1,2,1] pivot=3
→less=[1,2,1] equal=[3] greater=[6,8,10]
→[1,1,2,3,6,8,10]
Common mistakes
- Worst case consider nahi karna (sorted array mein last element pivot)
- Equal elements sirf less ya greater mein jaana unbalanced banata hai
Practice questions
- Random pivot selection implement karo
- Lomuto aur Hoare partition compare karo
Time
O(n log n) average, O(n²) worst