Esercizio - distribuzione esatta dei confronti di quicksort su 6 elementi e caso pessimo

---

Soluzione

1. Input ordinato. Con pivot l'ultimo (il massimo) ogni partizione lascia $n-1$ elementi da una parte: $5+4+3+2+1=15=\binom62$ confronti, sempre. Con pivot casuale la media non dipende dall'input: $C_6=2\cdot7\cdot H_6-24=14\cdot\frac{49}{20}-24=34{,}3-24=10{,}3$. È il vantaggio della randomizzazione: nessun input fissato è cattivo.

2. Probabilità del caso pessimo. Il totale $\binom n2$ si ottiene solo se in ogni sottoproblema il pivot è il minimo o il massimo (altrimenti la somma $\sum(m_i-1)$ delle taglie dei sottoproblemi diminuisce). Un sottoproblema di taglia $m\ge2$ ha $2$ pivot estremi su $m$, probabilità $\frac2m$, e il sottoproblema che resta ha taglia $m-1$. Dunque $$P\Big(C_n=\binom n2\Big)=\prod_{m=2}^n\frac2m=\frac{2^{n-1}}{n!}.$$ ($m=2$ ha probabilità $1$, perché entrambi gli elementi sono estremi.) $n=6$: $\frac{32}{720}=\frac2{45}\approx0{,}0444$. $n=10$: $\frac{512}{3\,628\,800}\approx1{,}4\cdot10^{-4}$.

3. Distribuzione di $C_6$. Il pivot ha rango $r=1..6$ (probabilità $\frac16$), costa $5$ e lascia taglie $r-1$ e $6-r$; i due sottoproblemi sono indipendenti. Servono le distribuzioni di $C_m$ per $m\le5$: $C_0=C_1=0$; $C_2=1$; $C_3\in\{2,3\}$ con $\frac13,\frac23$; $C_4\in\{4,5,6\}$ con $\frac12,\frac16,\frac13$; $C_5\in\{6,\dots,10\}$ con $\frac13,\frac4{15},\frac15,\frac1{15},\frac2{15}$. Componendo sui ranghi si ottiene:

cioè $\frac19,\frac7{18},\frac1{18},\frac29,\frac4{45},\frac1{15},\frac1{45},\frac2{45}$ (somma $\frac{90}{90}$ con denominatore comune $90$). Esempi: il valore $15$ viene da $r=1$ o $r=6$ con $C_5=10$: $\frac26\cdot\frac2{15}=\frac2{45}$ ✓ (la formula del punto 2). Il minimo $8$ si ha solo con $r=3$ o $r=4$ (taglie $2$ e $3$) e $C_3=2$: $5+1+2=8$, probabilità $\frac26\cdot\frac13=\frac19$ ✓. Media: $\frac{8\cdot10+9\cdot35+10\cdot5+11\cdot20+12\cdot8+13\cdot6+14\cdot2+15\cdot4}{90}=\frac{80+315+50+220+96+78+28+60}{90}=\frac{927}{90}=10{,}3$ ✓.

4. Markov. $P(C_6\ge12)\le\frac{10{,}3}{12}=0{,}858$. Il valore vero è $\frac8{90}+\frac6{90}+\frac2{90}+\frac4{90}=\frac{20}{90}=\frac29\approx0{,}222$. Per $C_6\ge2E[C_6]=20{,}6$ Markov dà $\le\frac12$, ma il massimo è $15$: la probabilità vera è $0$. Markov usa solo la media e quindi è molto largo (Disuguaglianze di Markov, Chebyshev e JensenMarkov: per X ≥ 0, P(X ≥ a) ≤ E[X]/a; Chebyshev: P(|X − μ| ≥ ε) ≤ Var(X)/ε²; Jensen: per φ convessa, φ(E[X]) ≤ E[φ(X)]. Stimano probabilità e medie conoscendo solo media e varianza.Disuguaglianze di Markov, Chebyshev e Jensen →).

5. Pivot fisso su input casuale. Con pivot l'ultimo e la sequenza una permutazione uniforme di sei elementi, il pivot ha rango uniforme in $\{1..6\}$ e, dato il rango, le due parti sono permutazioni uniformi dei rispettivi elementi: stessa ricorrenza di prima. Enumerando le $720$ permutazioni e applicando quicksort con pivot ultimo la media è $\frac{103}{10}=10{,}3$. La differenza con il punto 1: qui la casualità è nell'input, non nell'algoritmo, e un input ordinato costa sempre $15$.

Risultato. $15$ confronti (pivot fisso, input ordinato) contro $10{,}3$ in media (pivot casuale); $P(C_n=\binom n2)=\frac{2^{n-1}}{n!}$, $\frac2{45}$ per $n=6$; $E[C_6]=\frac{103}{10}$; $P(C_6\ge12)=\frac29$ contro il limite di Markov $0{,}858$.

Verifica Python: distribuzione esatta per composizione delle distribuzioni con Fraction (tutti i valori della tabella); enumerazione delle $720$ permutazioni con pivot ultimo: media $\frac{103}{10}$; simulazione con pivot casuale su input ordinato: media $10{,}30$ e frequenza di $15$ confronti $0{,}0443$ ($200\,000$ prove).