Quick sort — Lomuto - Hoare partition, pivot strategies, expected O(n log n), worst case

3.6.3 · Coding › Sorting & Searching

1. The skeleton

KYA cheez quicksort ko merge sort se alag karti hai: merge sort trivially split karta hai (middle index) aur kaam merging mein karta hai; quicksort kaam splitting mein karta hai aur trivially merge karta hai. Pivot choice hi algorithm hai.

2. Lomuto partition (aasaan wala)

Formula Lomuto pseudocode + invariant

partition(A, lo, hi):
    pivot = A[hi]
    i = lo - 1                  # i = "< pivot" zone ka last index
    for j in lo .. hi-1:
        if A[j] < pivot:
            i = i + 1
            swap A[i], A[j]
    swap A[i+1], A[hi]          # pivot ko zone ke baad rakh do
    return i + 1                # pivot ka final index

Loop invariant (iteration j se pehle):

$A [lo .. i] <$ pivot
$A [i + 1.. j - 1] \geq$ pivot
$A [hi]$ = pivot

Jab loop khatam hota hai, $A [i + 1.. hi - 1] \geq$ pivot, toh pivot ko index $i + 1$ par swap karna use sahi jagah rakhta hai.

Worked example Lomuto trace on

[3, 7, 8, 5, 2, 1, 9, 5_pivot] (pivot = 5)

step (j)	A[j]	<5?	i	array (zone in [])
start	–	–	-1	[ ]3 7 8 5 2 1 9 5
0	3	yes	0	[3] 7 8 5 2 1 9 5
1	7	no	0	[3] 7 8 5 2 1 9 5
2	8	no	0	[3] 7 8 5 2 1 9 5
3	5	no (==)	0	[3] 7 8 5 2 1 9 5
4	2	yes	1	[3 2] 8 5 7 1 9 5
5	1	yes	2	[3 2 1] 5 7 8 9 5
6	9	no	2	[3 2 1] 5 7 8 9 5
final swap	–	–	–	3 2 1 5 7 8 9 5 → pivot at index 3

Yeh step kyun? j=4 (value 2) par hum zone badhate hain aur 2 ko leftward swap karte hain — aise hi chhote elements left migrate karte hain. Ek final swap pivot ko zones ke beech bilkul sahi jagah gira deta hai.

3. Hoare partition (efficient original)

Formula Hoare pseudocode

partition(A, lo, hi):
    pivot = A[lo]               # aksar pehla element
    i = lo - 1
    j = hi + 1
    while true:
        do i = i+1  while A[i] < pivot
        do j = j-1  while A[j] > pivot
        if i >= j: return j      # NOTE: split point return karta hai, pivot ka final index NAHI
        swap A[i], A[j]

Crucial difference: Hoare ek boundary j return karta hai jaise ki [lo..j] ka har element $\leq$ [j+1..hi] ke har element se ho, lekin pivot ka index j par hona guaranteed nahi hai. Toh recursion hai quicksort(lo, j) aur quicksort(j+1, hi) — dhyan do j, na ki j-1/j+1.

4. Average $O (n lo g n)$ kyun — derive karo

Derivation (recurrence, balanced case). $T (n) = 2 T (n /2) + c n$ Master Theorem se ( $a = 2, b = 2, f (n) = c n$ , with $n^{l o g_{b} a} = n$ ): regular case deta hai $T (n) = Θ (n lo g n) .$

9-to-1 split bhi theek hai. Maan lo har split $\frac{1}{10}$ vs $\frac{9}{10}$ hai: $T (n) = T (n /10) + T (9 n /10) + c n .$ Sabse lamba root-to-leaf path har step mein $9/10$ factor se chhhota hota hai, toh depth $= lo g_{10/9} n = Θ (lo g n)$ , aur har level $\leq c n$ cost karta hai → phir bhi $Θ (n lo g n)$ .

Random pivots par average — comparisons count karo. Sorted order mein elements ko maan lo $z_{1} < z_{2} < \dots < z_{n}$ hain. Indicator $X_{ij} = 1$ maan lo agar $z_{i}$ aur $z_{j}$ kabhi bhi compare hote hain.

Yeh step kyun? "Gap se pehla pivot" argument ek messy recursion ko clean indicator-variable probabilities mein badal deta hai — yahi 80/20 insight hai jo memorize karne layak hai.

5. Worst case $O (n^{2})$ — aur isse kaise bachein

$T (n) = T (n - 1) + c n ⟹ T (n) = Θ (n^{2}) .$

Yeh Lomuto + last-element pivot ke saath already sorted (ya reverse-sorted) array par hota hai — classic gotcha.

Formula Pivot strategies (defenses)

Strategy	Idea	Worst case
First/last element	simple	$O (n^{2})$ sorted input par
Random pivot	uniformly random index pick karo, end par swap karo	Expected $O (n lo g n)$ ; adversary bad input force nahi kar sakta
Median-of-three	`A[lo], A[mid], A[hi]` ka median	Sorted-array worst case khatam; theoretically phir bhi $O (n^{2})$
Introsort	quicksort, heapsort par switch karo jab recursion depth $> 2 lo g n$ ho	Guaranteed $O (n lo g n)$

Figure — Quick sort — Lomuto - Hoare partition, pivot strategies, expected O(n log n), worst case

6. Properties summary

7. Active recall

Recall Quick self-test (answers cover karo)

Lomuto pivot ko end mein correctly kyun place karta hai? → invariant guarantee karta hai $A [i + 1.. hi - 1] \geq$ pivot, toh pivot $i + 1$ par belong karta hai.
Hoare ki return value ka kya matlab hai? → ek split boundary, pivot ka index nahi.
Do elements ke compare hone ki probability? → $2/ (j - i + 1)$ .
Last-element pivot ke saath worst case kab trigger hota hai? → sorted / reverse-sorted input.

Quicksort ki core idea kya hai?

Ek pivot chuno, partition karo taaki chhote elements left jaayein aur bade right (pivot final position mein land kare), phir dono sides par recurse karo.

Lomuto partition kya return karta hai?

Pivot ka final sorted index (i+1).

Hoare partition kya return karta hai?

Ek partition boundary j; pivot ka j par hona guaranteed NAHI hai, toh (lo,j) aur (j+1,hi) par recurse karo.

Hoare Lomuto se kam swaps kyun karta hai?

Yeh sirf genuinely out-of-place pairs ko do converging pointers se swap karta hai, bajaye har chhote element ko scan karte waqt swap karne ke.

Quicksort ki average time complexity kya hai aur kyun?

Θ(n log n); balanced (constant-fraction) splits O(log n) depth dete hain with O(n) work per level.

Sorted elements z_i aur z_j ke kabhi compare hone ki probability kya hai?

2/(j−i+1) — yeh tabhi compare hote hain jab unme se ek {z_i..z_j} se pehla pivot chuna jaaye.

Randomized quicksort ka expected comparison count kya hai?

Approximately 2n·H_n ≈ 1.39 n log₂ n = Θ(n log n).

Quicksort O(n²) kab hit karta hai?

Jab pivots consistently min/max hote hain, e.g. sorted/reverse-sorted input par last-element pivot, ek baar mein ek element peel karta hua.

Random pivot kaise help karta hai, aur kya fix NAHI karta?

Yeh kisi bhi fixed worst-case input ko hata deta hai (expected n log n), lekin worst case phir bhi O(n²) hai — bas astronomically unlikely.

Median-of-three kya hai?

A[lo], A[mid], A[hi] ka median pivot ki tarah choose karo sorted-array worst case se bachne ke liye.

Introsort kya hai?

Quicksort jo heapsort par switch kar leta hai jab recursion depth ~2 log n se zyada ho jaaye, O(n log n) guarantee karta hua.

Kya quicksort stable hai?

Nahi — swaps equal keys ko reorder kar sakte hain.

Stack space O(log n) kaise rakho?

Pehle chhote partition par recurse karo aur bade par loop (tail-call) karo.

Bahut saare duplicate keys efficiently kaise handle karein?

3-way (Dutch national flag) partition <, =, > mein aur equal block skip karo.

Recall Feynman: 12-saal ke bachche ko explain karo

Socho ek line of kids height ke hisaab se sort karni hai. Tum ek bacche ko pakad lete ho (pivot) aur kehte ho: "Jo mere se chhota hai, meri left mein khado; jo lamba hai, right mein." Ab woh baccha exactly wahin hai jahan belong karta hai — woh phir nahi hilega. Tum yahi game left group aur right group par alag alag repeat karte ho. Tab tak karo jab tak har chhota group mein ek baccha ho. Poori line sort ho gayi! Agar tum galti se hamesha sabse chhote bacche ko pivot choose karo, toh har round mein sirf ek baccha place hoga aur bahut time lagega — yahi slow case hai. Ek random baccha choose karna almost hamesha line ko achhi tarah split kar deta hai.

Connections

Merge Sort — yeh bhi divide & conquer hai, lekin stable aur guaranteed $n lo g n$ (kaam merge mein, split mein nahi).
Heap Sort — Introsort ke andar $O (n lo g n)$ fallback ki tarah use hota hai.
Master Theorem — $T (n) = 2 T (n /2) + c n$ recurrence solve karta hai.
Dutch National Flag Problem — duplicate keys ke liye 3-way partition.
Randomized Algorithms — random-pivot expectation argument.
Quickselect — same partition, $k$ -th smallest expected $O (n)$ mein dhundhne ke liye use hota hai.
Binary Search — already-sorted data par sibling "divide" idea.