Bucket sort — uniform distributions — Hinglish notes

3.6.8 · Coding › Sorting & Searching

WHAT it is

Woh assumption jo ise fast banati hai: inputs ek known interval par uniform distribution se drawn hain, isliye buckets evenly fill hote hain.

WHY it works — expected time scratch se derive karo

Hume expected total cost chahiye. Scatter, concatenation, aur bucket creation — teeno $O (n)$ hain. Risky part sirf buckets ko sort karna hai, kyunki size $m$ ke bucket par insertion sort $O (m^{2})$ leta hai.

Maano $n_{i}$ = bucket $i$ mein girne wale elements ki sankhya. Total sort cost: $T = O (n) + \sum_{i = 0}^{n - 1} O (n_{i}^{2})$

Expectation lo: $E [T] = O (n) + \sum_{i = 0}^{n - 1} O (E [n_{i}^{2}])$

Ab humein $E [n_{i}^{2}]$ chahiye. $n$ elements mein se har ek independently probability $p = 1/ n$ se bucket $i$ mein girta hai (uniform input → har bucket mein equal chance). Toh $n_{i} \sim Binomial (n, 1/ n)$ .

Identity $E [X^{2}] = Var (X) + (E [X])^{2}$ use karo: $E [n_{i}^{2}] = n p (1 - p) + (n p)^{2}$

$p = 1/ n$ plug karo: $E [n_{i}^{2}] = n \cdot \frac{1}{n} (1 - \frac{1}{n}) + (n \cdot \frac{1}{n})^{2} = (1 - \frac{1}{n}) + 1 = 2 - \frac{1}{n}$

Yahi toh punchline hai: $E [n_{i}^{2}]$ ek constant hai ( $< 2$ ), $n$ ke saath grow nahi karta. Toh: $E [T] = O (n) + \sum_{i = 0}^{n - 1} O (2 - \frac{1}{n}) = O (n) + O (n) = O (n)$

Figure — Bucket sort — uniform distributions

HOW to implement it

def bucket_sort(a):           # a: list of floats in [0, 1)
    n = len(a)
    buckets = [[] for _ in range(n)]      # n empty buckets
    for x in a:
        buckets[int(n * x)].append(x)     # scatter: index = floor(n*x)
    out = []
    for b in buckets:
        b.sort()                          # insertion sort in practice
        out.extend(b)                     # concatenate in order
    return out

int(n*x) kyun? $[0, 1)$ ko $n$ se stretch karne par value directly ek bucket address par map ho jaati hai, isliye equal-width slots equal value-ranges ke correspond karte hain.

Jab yeh FAIL hota hai (steel-man)

Recall Feynman: ek 12-saal ke bachche ko samjhao

Socho 100 bacche hain, har ek ke paas 0 se 99 tak koi number likha card hai, aur tumhe unhe smallest se largest mein line mein lagana hai. Cards ek-ek karke compare karne ki jagah, tum 100 labeled boxes rakh do (0,1,2,...). Har bachcha apna card us box mein daalta hai jo uske number ke pehle digit se match kare. Kyunki numbers evenly spread hain, almost har box mein sirf ek card aata hai. Phir boxes ko left se right padhte jao — ho gaya! Trick yeh hai: number khud batata hai kahan jaana hai, isliye sort almost karna hi nahi padta.

Recall checkpoint

Bucket sort: kaun si input distribution expected

O (n)

deti hai?

Ek known range par uniform distribution (taaki buckets evenly fill hon).

Bucket sort:

n

buckets ke saath

x \in [0, 1)

value ke liye bucket index ka formula?

⌊ n \cdot x ⌋

Bucket sort: worst-case time aur kab hota hai?

O (n^{2})

, jab saare elements ek bucket mein girte hain (skewed/adversarial input).

Comparison-sort lower bound

Ω (n lo g n)

bucket sort par kyun apply nahi hota?

Scatter step value ko address ki tarah use karta hai (comparisons nahi), isliye yeh comparison sort nahi hai.

n_{i} \sim Binomial (n, 1/ n)

ke liye,

E [n_{i}^{2}]

kya hai?

2 - 1/ n

(ek constant

< 2

), isliye total sort work

O (n)

hai.

E [X^{2}]

, variance aur mean ko kaun si identity link karti hai?

E [X^{2}] = Var (X) + (E [X])^{2}

Roughly kitne buckets use karne chahiye, aur kyun?

\approx n

— expected element ke hisaab se ek; bahut kam se collisions hote hain, bahut zyada se empty buckets par time waste hota hai.

[0, 1)

ki jagah

[l o, hi)

mein values ko bucket-sort kaise karte hain?

Index

= ⌊ n (x - l o) / (hi - l o)⌋

(pehle normalize karo).

Kya bucket sort stable hai?

Haan, agar har bucket ka internal sort stable ho aur elements insertion order maintain karein.

Connections

Counting sort — integers par bucket size 1 wala bucket sort.
Radix sort — digit by digit repeated bucketing.
Insertion sort — per-bucket sort, tiny/near-sorted lists par fast.
Comparison sort lower bound — kyun non-comparison sorts $n lo g n$ ko beat kar sakte hain.
Binomial distribution — analysis mein $E [n_{i}^{2}]$ deta hai.
Hashing — wahi "value-as-address" idea, alag goal.