Linear time selection — median of medians algorithm

3.6.10 · Coding › Sorting & Searching

HUM ACTUALLY KYA SOLVE KAR RAHE HAIN?

Sort kyun nahi karte? Sorting se saare order statistics milte hain lekin cost aati hai $O (n lo g n)$ . Hume chahiye sirf ek. Zaroorat se zyada kaam karna wahi cheez hai jo 80/20 kehta hai avoid karo — isliye hum aim karte hain $O (n)$ ke liye.

Quickselect KAISE kaam karta hai (foundation)

Quickselect = Quicksort jo sirf usi side mein recurse karta hai jisme $k$ hai.

Ek pivot $p$ chuno.
$A$ ko $p$ ke around partition karo: chhote elements left mein, bade right mein. Pivot apni final sorted index $i$ par aa jaata hai.
Agar $i = k$ → kaam khatam. Agar $k < i$ → left mein recurse karo. Agar $k > i$ → right mein recurse karo ( $k$ adjust karo).

Trick: Median of Medians pivot choose karta hai

5 kyun? Yeh sabse chhota odd group size hai jiske liye recursion math close ho jaata hai (linear time deta hai). Hum derivation mein exactly dekhenge ki 5 kahan se aata hai. (Groups of 3 fail karte hain; 7 bhi kaam karta hai lekin 5 practice mein optimal hai.)

Figure — Linear time selection — median of medians algorithm

YEH pivot provably accha kyun hai (dil ki baat)

Maano $M$ un $⌈ n /5 ⌉$ group-medians ka median hai. Hum bound karte hain ki kitne elements $M$ se chhote hain (aur symmetry se, bade).

Symmetry se, kam se kam $\frac{3 n}{10}$ elements $\geq M$ hain. Isliye partition ki badi side mein zyada se zyada $n - \frac{3 n}{10} = \frac{7 n}{10}$ elements hain.

Worked example 1 — pivot $M$ nikalna

Array (n=15): [12, 3, 5, 7, 19, 1, 8, 22, 4, 6, 15, 9, 2, 11, 17], chahiye $k = 8$ (median).

Step 1 — groups of 5. [12,3,5,7,19] [1,8,22,4,6] [15,9,2,11,17] Kyun? Constant-size groups har group ka median trivial bana dete hain.

Step 2 — har group ka median (5 sort karo, beech wala lo):

[3,5,7,12,19] → 7
[1,4,6,8,22] → 6
[2,9,11,15,17] → 11

Step 3 — median of medians [7,6,11] ka → 7. Toh pivot $M = 7$ . Yeh kyun matter karta hai: 7 guarantee ke saath extreme ke paas nahi hoga, isliye iske around partition karna constant fraction hata deta hai.

Step 4 — 7 ke around partition: elements $< 7$ : [3,5,1,4,6,2] (6 hain) → 7 index 7 par land karta hai (1-indexed). Kyunki $k = 8 > 7$ , right mein recurse karo [12,19,8,22,15,9,11,17] ke liye $(8 - 7) = 1$ st smallest = 8. ✅ (8 wakai original ka median hai.)

Worked example 2 — bura pivot kyun nuksaan karta (steel-man)

Same array, lekin maano pivot = 1 (min) chuna.

Partition: left mein kuch nahi, 1 index 1 par land karta hai. Hume baki 14 elements mein recurse karna padega. Humne $O (n)$ kaam ke liye sirf ek element hataya.

Yeh step danger kyun dikhata hai: agar har pivot min/max hota, toh hum karte $O (n) + O (n - 1) + \dots = O (n^{2})$ . MoM yeh rok deta hai kyunki $M$ ke hamesha har side par $\geq \frac{3 n}{10}$ elements hote hain.

Common mistakes (Steel-man them)

Forecast-then-Verify

Pseudocode (self-contained)

Select(A, k):
    if len(A) <= 5:
        return sorted(A)[k-1]
    medians = [median(group) for group in chunks(A, 5)]
    M = Select(medians, ceil(len(medians)/2))      # median of medians
    L = [x for x in A if x < M]
    E = [x for x in A if x == M]
    G = [x for x in A if x > M]
    if k <= len(L):           return Select(L, k)
    elif k <= len(L)+len(E):  return M
    else:                     return Select(G, k - len(L) - len(E))

3-way split (L, E, G) kyun? Yeh $M$ ke duplicates ko safely handle karta hai taaki hum kabhi bhi aise side par recurse na karein jo shrink nahi ho sakti.

Flashcards

What problem does selection solve?

k

-th sabse chhota element (k-th order statistic) dhundhna bina puri tarah sort kiye.

Why can plain Quickselect be

O (n^{2})

Consistently bura pivot (min/max) har call mein sirf ek element hataata hai.

What is the median-of-medians pivot rule?

Groups of 5 mein baanto, har group ka median lo, unhi medians ka median recursively select karo pivot ki tarah.

How many elements are guaranteed

\leq M

(the MoM pivot)?

Kam se kam

3 n /10

(lagbhag

n /5

groups mein se aadhe mein se 3 per group).

What is the MoM recurrence?

T (n) \leq T (n /5) + T (7 n /10) + c n

Why does that recurrence give

O (n)

Kyunki

1/5 + 7/10 = 9/10 < 1

;

T (n) \leq an

substitute karne par

a \geq 10 c

chahiye, isliye

T (n) = O (n)

Why does group size 3 fail?

Guarantee girke

n /3

per side ho jaati hai; recurrence ka sum

1/3 + 2/3 = 1

hota hai,

< 1

nahi, toh linear nahi.

Why use MoM over random pivots in practice?

Sirf guaranteed worst-case

O (n)

ke liye; random average par faster hai lekin worst case

O (n^{2})

hai.

Why the 3-way (L,E,G) partition?

Pivot ke duplicates ko sahi se handle karne ke liye aur ensure karna ki recursive side hamesha shrink ho.

Which fraction inequality is the crux of linearity?

Recursive-size fractions ka sum strictly 1 se kam hona chahiye.

Recall Feynman: 12-saal ke bachche ko samjhao

Maano 15 bachche hain aur tumhe woh bachcha dhundhna hai jo beech ki height ka ho — lekin sabko line mein lagana bahut time leta hai. Trick: bacchon ko chhoti-chhoti teams of 5 mein baanto. Har team mein, beech wali height ka bachcha dhundho. Ab sirf unhi beech wale bacchon ko dekho aur unka beech wala dhundho. Woh bachcha "kaafi beech wala" hoga — kabhi sabse chhota ya sabse lamba nahi hoga. Usse chhote wale left mein khade ho jaayein, bade wale right mein. Jis side mein tumhara chahiya hua bachcha ho, wahan dobara yahi game khelate raho. Kyunki har round mein bacchon ka ek bada hissa hata diya jaata hai, tum bahut jaldi khatam ho jaate ho — aur trick guarantee deti hai ki tumhara luck kabhi kharaab nahi hoga.

Connections

Quickselect — MoM woh pivot-choosing upgrade hai jo ise worst-case linear banata hai.
Quicksort — same partition machinery; MoM pivot worst-case $O (n lo g n)$ quicksort deta hai.
Order statistics — median, min, max selection ke special cases hain.
Master Theorem / Recurrence relations — lekin note karo ki MoM ko substitution chahiye, Master Theorem nahi (unequal subproblems).
Randomized algorithms — contrast: expected vs worst-case guarantees.
Partitioning (Lomuto vs Hoare) — step 4 ke peeche ka engine.