Esercizio - confronti attesi di quicksort su 5 elementi, tre metodi

---

Soluzione

1. Coppie. Con le chiavi ordinate $z_1<\dots<z_5$, la coppia $(z_i,z_j)$ è confrontata con probabilità $\frac2{j-i+1}$ (il primo pivot scelto tra $z_i..z_j$ deve essere uno dei due estremi). Per distanza $d=j-i$:

• $d=1$: $4$ coppie, probabilità $\frac22=1$, contributo $4$;
• $d=2$: $3$ coppie, $\frac23$, contributo $2$;
• $d=3$: $2$ coppie, $\frac24=\frac12$, contributo $1$;
• $d=4$: $1$ coppia, $\frac25$, contributo $0{,}4$.

$E[C_5]=4+2+1+0{,}4=7{,}4$.

2. Formula e ricorrenza. $H_5=1+\frac12+\frac13+\frac14+\frac15=\frac{137}{60}$, quindi $2\cdot6\cdot\frac{137}{60}-4\cdot5=\frac{137}5-20=27{,}4-20=7{,}4$.

Ricorrenza, con $C_0=C_1=0$ (usati come valori attesi): $C_2=1+\frac22(C_0+C_1)=1$; $C_3=2+\frac23(0+0+1)=\frac83$; $C_4=3+\frac24(0+0+1+\frac83)=3+\frac12\cdot\frac{11}3=\frac{29}6$; $C_5=4+\frac25\big(0+0+1+\frac83+\frac{29}6\big)=4+\frac25\cdot\frac{6+16+29}6=4+\frac25\cdot\frac{51}6=4+\frac{17}5=\frac{37}5=7{,}4$. ✓

3. Distribuzione. Il pivot ha rango $r\in\{1..5\}$ con probabilità $\frac15$; costa $4$ e lascia sottoproblemi di taglia $r-1$ e $5-r$. Costi delle taglie piccole: taglie $0,1$: $0$; taglia $2$: $1$; taglia $3$: pivot centrale (probabilità $\frac13$) costa $2$, pivot estremo ($\frac23$) costa $2+1=3$, quindi $C_3\in\{2,3\}$ con probabilità $\frac13,\frac23$; taglia $4$: i pivot di rango $2,3$ (probabilità $\frac12$) costano $3+0+1=4$, quelli di rango $1,4$ costano $3+C_3$, cioè $5$ con probabilità $\frac12\cdot\frac13=\frac16$ e $6$ con $\frac12\cdot\frac23=\frac13$. Per i ranghi del pivot su $5$ elementi:

• $r=3$ (probabilità $\frac15$): $4+C_2+C_2=4+1+1=6$;
• $r=2,4$ (probabilità $\frac25$): $4+C_1+C_3=4+C_3$, cioè $6$ con $\frac25\cdot\frac13=\frac2{15}$ e $7$ con $\frac25\cdot\frac23=\frac4{15}$;
• $r=1,5$ (probabilità $\frac25$): $4+C_4$, cioè $8$ con $\frac15$, $9$ con $\frac2{5}\cdot\frac16=\frac1{15}$ e $10$ con $\frac25\cdot\frac13=\frac2{15}$.

Il valore $6$ ha probabilità $\frac15+\frac2{15}=\frac13$.

Distribuzione risultante:

Media: $\frac{6\cdot5+7\cdot4+8\cdot3+9\cdot1+10\cdot2}{15}=\frac{30+28+24+9+20}{15}=\frac{111}{15}=7{,}4$. ✓

4. Markov. $P(C_5\ge10)\le\frac{E[C_5]}{10}=0{,}74$. Il valore vero è $\frac2{15}\approx0{,}133$: Markov è utile solo per dare una garanzia generale (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 →).

Risultato. $E[C_5]=\frac{37}5=7{,}4$ con tutti e tre i metodi; $C_5\in\{6,\dots,10\}$ con probabilità $\frac13,\frac4{15},\frac15,\frac1{15},\frac2{15}$; $P(C_5\ge10)=\frac2{15}$ contro il limite di Markov $0{,}74$.

Verifica Python: ricorrenza e distribuzione esatte con Fraction, simulazione di $100\,000$ esecuzioni di quicksort: media $7{,}40$.