Esercizio - quali coppie vengono confrontate, confronti del minimo e della mediana in quicksort

---

Soluzione

1. Probabilità. Per il lemma $P=\frac2{j-i+1}$.

• $z_3,z_7$: $j-i+1=5$, $P=\frac25$.
• $z_1,z_{10}$: $j-i+1=10$, $P=\frac15$ (sono confrontati solo se il primo pivot dell'intero insieme è uno dei due estremi).
• Adiacenti ($j=i+1$): $P=\frac22=1$, perché tra i due non ci sono elementi che possano separarli: prima o poi uno dei due è pivot mentre l'altro è ancora nel suo problema.

2. Confronti di un elemento. Sia $Y_r$ il numero di confronti che coinvolgono $z_r$. Per linearità $E[Y_r]=\sum_{j\ne r}P(z_r,z_j\text{ confrontati})=\sum_{j\ne r}\frac2{|j-r|+1}$.

• $r=1$: $\sum_{j=2}^{10}\frac2j=2(H_{10}-1)=2\cdot1{,}9290=3{,}858$.
• $r=5$: a destra (distanze $d=1..5$, dunque $j-r+1=2..6$): $2(H_6-1)=2\cdot1{,}45=2{,}9$; a sinistra ($d=1..4$, valori $2..5$): $2(H_5-1)=2\cdot1{,}2833=2{,}5667$. Totale $5{,}467$.

In generale $E[Y_r]=2(H_r-1)+2(H_{n-r+1}-1)$: il minimo e il massimo sono confrontati meno degli elementi centrali, ma di poco ($3{,}86$ contro $5{,}47$ con $n=10$).

3. Somma. Ogni confronto coinvolge due elementi, quindi $\sum_rY_r=2C_n$ e $\sum_rE[Y_r]=2E[C_n]$. Calcolando i dieci valori $E[Y_r]$ per $r=1..10$ e sommando si ottiene $48{,}875$, e $2E[C_{10}]=2\,(2\cdot11\cdot H_{10}-40)=2\cdot24{,}437=48{,}875$. ✓

4. Dimostrazione del lemma. Sia $Z_{ij}=\{z_i,\dots,z_j\}$. Finché nessun elemento di $Z_{ij}$ è stato scelto come pivot, i suoi elementi stanno nello stesso sottoproblema: un pivot esterno è minore o maggiore di tutti, quindi li lascia insieme. Il primo elemento di $Z_{ij}$ scelto come pivot è uniforme su $Z_{ij}$ (ogni pivot è scelto a caso nel proprio sottoproblema, che contiene tutto $Z_{ij}$). Se è $z_i$ o $z_j$, i due vengono confrontati; se è interno, li separa e non saranno mai confrontati. La probabilità è $\frac2{j-i+1}$. $\square$

Risultato. $\frac25$, $\frac15$ e $1$; $E[Y_1]=2(H_{10}-1)\approx3{,}858$, $E[Y_5]\approx5{,}467$; $\sum_rE[Y_r]=48{,}875=2E[C_{10}]$.

Verifica Python: le probabilità sono calcolate con la ricorrenza esatta sul rango del pivot (pcomp: $\frac25$, $1$, $\frac15$) e coincidono con $\frac2{j-i+1}$; simulazione dei confronti del minimo e della mediana su $60\,000$ esecuzioni: $3{,}856$ e $5{,}481$.