Esercizio - quickselect, confronti attesi per il minimo, la mediana e il massimo

Soluzione

1. Esecuzione. Ogni passo costa (taglia $-1$) confronti.

• Pivot $8$ su $[7,3,9,1,5,8]$: $5$ confronti; $lo=[7,3,1,5]$, $hi=[9]$. Poiché $k=3\le|lo|=4$ si prosegue su $lo$.
• Pivot $3$ su $[7,3,1,5]$: $3$ confronti; $lo=[1]$, $hi=[7,5]$. Poiché $k=3>|lo|+1=2$, si cerca in $hi$ l'elemento di rango $k=3-2=1$.
• Pivot $7$ su $[7,5]$: $1$ confronto; $lo=[5]$, e $k=1\le1$ si prosegue su $[5]$: un solo elemento, la risposta è $5$ (che è il terzo più piccolo: $1,3,5,7,8,9$).

Totale $5+3+1=9$ confronti.

2. Ricorrenza esatta. Il pivot ha rango $r$ uniforme; costa $n-1$; se $r=k$ ci si ferma, se $r>k$ si prosegue nei $r-1$ elementi minori con lo stesso $k$, se $r<k$ nei $n-r$ maggiori con $k-r$: $$Q(n,k)=n-1+\frac1n\Big(\sum_{r>k}Q(r-1,k)+\sum_{r<k}Q(n-r,k-r)\Big),\quad Q(1,\cdot)=0.$$ Valori piccoli: $Q(2,1)=1$ ($r=1$ ferma, $r=2$ ricade su $Q(1,1)=0$). Per $n=5$, $k=1$: $Q(5,1)=4+\frac15\big(Q(1,1)+Q(2,1)+Q(3,1)+Q(4,1)\big)$ con $Q(3,1)=2+\frac13(0+1)=\frac73$ e $Q(4,1)=3+\frac14\big(0+1+\frac73\big)=3+\frac14\cdot\frac{10}3=\frac{23}6$, quindi $Q(5,1)=4+\frac15\big(0+1+\frac73+\frac{23}6\big)=4+\frac15\cdot\frac{43}{6}=\frac{163}{30}\approx5{,}433$. Per $k=3$ il calcolo analogo dà $Q(5,3)=\frac{101}{15}\approx6{,}733$: la mediana costa più del minimo, perché il pivot ha più probabilità di lasciare un sottoproblema grande.

3. Formula chiusa. Con $H_{10}=2{,}92897$:

• $k=1$: $2\big(13+11H_{10}-3H_1-12H_{10}\big)=2(13-H_{10}-3)=2(10-H_{10})=14{,}142$ (cioè $2(n-H_n)$);
• $k=10$: stesso valore per simmetria, $14{,}142$;
• $k=5$: $2\big(13+11H_{10}-7H_5-8H_6\big)=2\big(13+32{,}2187-15{,}9833-19{,}6\big)=2\cdot9{,}6354=19{,}271$.

Quicksort su $10$ chiavi costa $2\cdot11H_{10}-40=24{,}437$: trovare la mediana costa $79\%$ di un ordinamento a $n=10$, ma per $n$ grande il rapporto scende (lineare contro $n\ln n$).

4. $n=1001$, $k=501$. La formula dà $Q=3339{,}7$, cioè $3{,}336\,n$; il limite $4n=4004$ è rispettato e $2(1+\ln2)\,n=3{,}386\,n\approx3389{,}7$ è una buona approssimazione (differenza $1{,}5\%$, dovuta ai termini di ordine inferiore).

import random
def qselect(a, k):
    c = 0
    while True:
        if len(a) == 1: return c
        p = random.choice(a); c += len(a) - 1
        lo = [x for x in a if x < p]; hi = [x for x in a if x > p]
        if k <= len(lo): a = lo
        elif k == len(lo) + 1: return c
        else: k -= len(lo) + 1; a = hi
print(sum(qselect(list(range(1, 1002)), 501) for _ in range(5000)) / 5000)   # circa 3340

Risultato. Esecuzione a mano: $9$ confronti. $Q(5,1)=\frac{163}{30}$, $Q(5,3)=\frac{101}{15}$; $n=10$: $14{,}14$ ($k=1,10$) e $19{,}27$ ($k=5$); $n=1001$, mediana: $3339{,}7\approx3{,}34\,n<4n$.

Verifica Python: ricorrenza esatta con Fraction e formula chiusa coincidono su tutti i casi (anche $n=2,10,11,20$); simulazioni: $n=10$, $k=5$: $19{,}30$; $n=1001$, $k=501$: $3345{,}8$ su $6000$ prove.