Quick sort randomization — expected O(n log n)

3.6.4 · Coding › Sorting & Searching

Randomized quicksort KIYA hai?

QUICKSORT(A, lo, hi):
    if lo < hi:
        r = RANDOM(lo, hi)          # <-- sirf yahi naya line hai
        swap A[r] with A[hi]        # random pivot ko end pe move karo
        p = PARTITION(A, lo, hi)    # Lomuto/Hoare around A[hi]
        QUICKSORT(A, lo, p-1)
        QUICKSORT(A, p+1, hi)

Cost kaise count hoti hai — comparisons hi sab kuch hain

Quicksort ka asli kaam comparisons mein hota hai jo partitioning ke dauran hoti hain. Toh agar hum expected comparisons ko bound kar lein, toh runtime bound ho jaata hai.

Key probability (ise derive karo!)

Yeh step kyun? $Z_{ij}$ ke har element ka same chance hai pehle pivot pick hone ka — yahi uniform randomization ka poora fayda hai. $j - i + 1$ mein se do favorable choices → probability $2/ (j - i + 1)$ .

Sum karo → bound milta hai

$E [X] = \sum_{i = 1}^{n - 1} \sum_{j = i + 1}^{n} \frac{2}{j - i + 1}$

$k = j - i$ substitute karo (toh $j - i + 1 = k + 1$ ). Har $i$ ke liye, $k$ $1$ se $n - i$ tak jaata hai:

$E [X] = \sum_{i = 1}^{n - 1} \sum_{k = 1}^{n - i} \frac{2}{k + 1} < \sum_{i = 1}^{n - 1} \sum_{k = 1}^{n} \frac{2}{k} = \sum_{i = 1}^{n - 1} 2 H_{n}$

jahan $H_{n} = \sum_{k = 1}^{n} \frac{1}{k}$ harmonic number hai, aur $H_{n} = Θ (ln n)$ .

$E [X] < 2 (n - 1) H_{n} = O (n lo g n)$

Figure — Quick sort randomization — expected O(n log n)

Worked examples

Common mistakes

Active recall

Recall Khud test karo (koshish ke baad kholna)

Quicksort mein do elements kab compare hote hain? → sirf jab ek pivot hota hai.
$Pr [z_{i} \leftrightarrow z_{j}] = \frac{2}{j - i + 1}$ kyun hai? → $Z_{ij}$ mein pehla pivot decide karta hai; $j - i + 1$ mein se 2 good.
Randomization adversary ko kyun beat karta hai? → cost coin flips par depend karti hai, input order par nahi.
Randomized quicksort ka worst case? → abhi bhi $O (n^{2})$ (bas improbable hai).

Randomization quicksort ki complexity mein kya change karta hai?

Worst case

O (n^{2})

rehta hai lekin expected time har input ke liye

O (n lo g n)

ho jaata hai; koi bhi input adversarially bura nahi hota.

Quicksort mein do elements

z_{i}, z_{j}

kab compare hote hain?

Tab jab unme se ek pivot choose hota hai jabki dono abhi bhi same subarray mein hain — zyada se zyada ek baar.

Pr [z_{i} and z_{j} are compared]

kya hai?

\frac{2}{j - i + 1}

, kyunki unke beech ke

j - i + 1

elements mein se (inclusive) pehla pivot

z_{i}

z_{j}

hona chahiye.

Indicator

X_{ij}

0 ya 1 hi kyun hota hai?

Ek pair zyada se zyada ek baar compare hota hai kyunki involved pivot future recursion se remove ho jaata hai; opposite-side elements kabhi compare nahi hote.

E [X]

closed form mein kya hai?

E [X] = \sum_{i < j} \frac{2}{j - i + 1} < 2 (n - 1) H_{n} = O (n lo g n)

, jahan

H_{n} = Θ (ln n)

Harmonic number

H_{n}

asymptotically kya hai?

H_{n} = \sum_{k = 1}^{n} 1/ k \approx ln n + 0.577

, toh

Θ (lo g n)

Do adjacent (sorted order mein) elements ke compare hone ki probability?

\frac{2}{2} = 1

— adjacent elements hamesha compare hote hain.

Kya start mein ek random shuffle random pivots jitna hi kaam karta hai?

Haan — dono pivot ranks ko uniformly random banate hain, same expected

O (n lo g n)

dete hain.

Recall Feynman: ek 12-saal ke bachche ko samjhao

Socho tum cards ki ek deck sort kar rahe ho ek card pick karke ("splitter"), phir chhote cards left mein aur bade cards right mein rakhke, aur har pile par repeat karte ho. Agar tum hamesha sabse chhota card splitter pick karo, toh piles ek taraf jhuk jaati hain (1 vs baaki sab) aur bahut time lagta hai. Trick yeh hai: har baar splitter card randomly pick karo. Ab koi sneaky tarika nahi hai ki koi deck arrange kare tumhe slow karne ke liye — kyunki woh guess nahi kar sakte tum kaun sa card utha loge. Average par tumhari piles nicely half-half split ho jaati hain, toh tum $n^{2}$ ke bajaye lagbhag $n lo g n$ steps mein finish karte ho. Do cards directly tab compare hote hain jab unme se ek splitter hota hai jabki woh abhi bhi same pile mein hain — aur yahi woh neat fraction $2/ (gap + 1)$ deta hai.

Connections

Quicksort (deterministic) — same partition logic, sorted input par worst-case $O (n^{2})$ .
Linearity of Expectation — woh engine jo hume per-pair probabilities sum karne deta hai.
Indicator Random Variables — $X_{ij}$ technique randomized algorithms mein baar baar use hoti hai.
Harmonic Number $H_{n} = Θ (ln n)$ — $lo g$ factor ka source.
Merge Sort — deterministic guaranteed $O (n lo g n)$ , stability/space par contrast.
Median of Medians — deterministic good-pivot selection, randomizing ka alternative.
Las Vegas vs Monte Carlo algorithms — quicksort Las Vegas hai (hamesha correct, time random).