Esercizio - inversioni di una permutazione casuale e confronti dell'insertion sort

---

Soluzione

1. Inversioni. Per ogni coppia di posizioni $i<j$ sia $I_{ij}=1$ se $a_i>a_j$. I due valori sono distinti e l'ordine relativo è uniforme: $P(I_{ij}=1)=\frac12$. Le coppie sono $\binom n2$: $$E[\#\text{inversioni}]=\binom n2\cdot\frac12=\frac{n(n-1)}4.$$ Per $n=5$: $\frac{20}4=5$. Enumerando le $120$ permutazioni il totale delle inversioni è $600$, media $5$ (le $I_{ij}$ sono dipendenti, ma non serve).

2. Confronti dell'insertion sort. Alla iterazione $i$ ($i=1..n-1$) l'elemento $a_i$ scorre a sinistra confrontandosi con i predecessori maggiori (ognuno è un confronto vero e una inversione risolta). Poi si ferma: o perché trova un predecessore minore (un confronto falso), o perché è arrivato in testa (nessun confronto in più). Quindi $$\#\text{confronti}=\#\text{inversioni}+\#\{i\in[1,n-1]:a_i\text{ non è un nuovo minimo del prefisso}\}.$$ $a_i$ è un nuovo minimo del prefisso $a_0..a_i$ con probabilità $\frac1{i+1}$ (come per i record: Linearità del valore atteso e variabili indicatriciLa linearità $E[X+Y]=E[X]+E[Y]$ vale sempre, anche senza indipendenza; con le variabili indicatrici ($E[I_A]=P(A)$) trasforma un conteggio in una somma di probabilità. Applicazioni: attesa del primo successo $1/p$, collezionista di figurine $nH_n$, punti fissi di una permutazione (media $1$), record (media $H_n$), inversioni ($n(n-1)/4$), attesa condizionata, identità di Wald $E[S_N]=E[N]E[X]$.Linearità del valore atteso e variabili indicatrici →). Gli $i$ tra $1$ e $n-1$ che sono nuovi minimi sono in media $\sum_{i=1}^{n-1}\frac1{i+1}=H_n-1$. I confronti falsi sono $(n-1)$ meno questi: $$E[\#\text{confronti}]=\frac{n(n-1)}4+(n-1)-(H_n-1).$$ Per $n=5$: $5+4-\big(\frac{137}{60}-1\big)=9-\frac{77}{60}=\frac{463}{60}\approx7{,}717$. Il caso peggiore ($n(n-1)/2=10$) è lontano, il migliore ($n-1=4$) pure: la media è quadratica ($\Theta(n^2)$) ma con costante $\frac14$.

3. Controllo su $[5,2,9,1,6]$. Le inversioni sono $(5,2),(5,1),(2,1),(9,1),(9,6)$, cioè $5$. I nuovi minimi del prefisso agli indici $1..4$ sono $2$ (indice 1) e $1$ (indice 3): $2$ di $4$. I confronti falsi sono $4-2=2$ e il totale è $5+2=7$, il valore dell'esecuzione a mano (Algoritmi di ordinamentoSelection sort e insertion sort (quadratici, con invarianti), merge sort (divide et impera, Theta(n log n)), quick sort (caso pessimo quadratico, medio n log n), heap sort (in loco, Theta(n log n)), ordinamento senza confronti per chiavi intere in un intervallo piccolo, limite inferiore Omega(n log n) per gli algoritmi basati su confronti.Algoritmi di ordinamento →).

Risultato. $E[\#\text{inversioni}]=\frac{n(n-1)}4$ ($5$ per $n=5$); $E[\#\text{confronti}]=\frac{n(n-1)}4+n-H_n$ ($\frac{463}{60}\approx7{,}717$ per $n=5$).

Verifica Python: enumerazione di tutte le permutazioni con un insertion sort che conta i confronti: medie esatte $\frac{59}{12}$ ($n=4$), $\frac{463}{60}$ ($n=5$), $\frac{221}{20}$ ($n=6$), uguali alla formula; per $[5,2,9,1,6]$ il codice conta $7$.