Algoritmi di ordinamento

In questa pagina 9

Problema. Input: sequenza $S[0..n-1]$ di chiavi confrontabili. Output: gli stessi elementi in ordine crescente (vedi Problemi computazionali e algoritmi). La taglia è $n$ . Qui si studiano algoritmi basati su confronti (le chiavi si usano solo con $<$ , $\le$ , $=$ , cioè l'ordine totale dei numeri reali: Campi ordinati (Q e R)). Gli stessi problemi sono trattati in modo più elementare in Fondamenti di Informatica (Ricerca lineare e binaria, Ordinare e cercare in C - qsort, bsearch e puntatori a funzione); qui l'attenzione è sull'analisi della complessità. Gli algoritmi ricorsivi seguono Algoritmi ricorsivi (Ricorsione) e le somme sono quelle di Sommatorie.

Per confrontare gli algoritmi si seguono tutti sullo stesso array $S=[5,2,9,1,6]$ ( $n=5$ ). L'ordine finale è $[1,2,5,6,9]$ .

Nota sulle fonti: insertion sort e selection sort compaiono nel materiale del corso (esercizi su complessità e invarianti); merge sort, quick sort, heap sort e il limite inferiore sono scritti dal programma ufficiale con conoscenze standard.

Selection sort

Si cerca il minimo della parte non ordinata e lo si porta in posizione $i$ .

Algoritmo selectionSort(S, n)
for i <- 0 to n-2 do
    minIndex <- i
    for k <- i+1 to n-1 do
        if S[k] < S[minIndex] then minIndex <- k
    swap(S[i], S[minIndex])

Proprietà (selection sort: invariante e costo). Invariante all'inizio dell'iterazione $i$ : $S[0..i-1]$ contiene gli $i$ elementi minori, già in ordine crescente (e ciascuno $\le$ tutti gli elementi di $S[i..n-1]$ ). Alla fine $i = n-1$ e tutto è ordinato. Costo: il ciclo interno fa $n - 1 - i$ confronti, in totale $\sum_{i=0}^{n-2}(n-1-i) = \frac{n(n-1)}{2} \in \Theta(n^2)$ per ogni istanza, anche già ordinata. Corrisponde alla coda con priorità su lista non ordinata (vedi Code con priorità).

Traccia (in grassetto la parte già ordinata; min è la posizione del minimo trovato):

$i$	minimo di $S[i..4]$	array dopo lo scambio	confronti
0	$1$ in posizione 3	$[\mathbf{1},2,9,5,6]$	4
1	$2$ in posizione 1 (resta)	$[\mathbf{1},\mathbf{2},9,5,6]$	3
2	$5$ in posizione 3	$[\mathbf{1},\mathbf{2},\mathbf{5},9,6]$	2
3	$6$ in posizione 4	$[\mathbf{1},\mathbf{2},\mathbf{5},\mathbf{6},9]$	1

Totale $4+3+2+1=10=\frac{5\cdot4}{2}$ . Il numero di scambi invece è al più $n-1$ (uno per iterazione): conta solo la parte di confronti.

Esempio. Con $n=5$ il selection sort fa $5\cdot4/2=10$ confronti su qualunque array, anche già ordinato.

Insertion sort

Proprietà (insertion sort: caso pessimo e caso migliore). Si mantiene ordinato un prefisso e si inserisce $S[i]$ al posto giusto spostando a destra i maggiori (pseudocodice e analisi in Complessità in tempo e caso pessimo). Invariante: all'inizio dell'iterazione $i$ , $S[0..i-1]$ è ordinato (e contiene gli elementi originali di $S[0..i-1]$ ). Caso pessimo $\Theta(n^2)$ (array decrescente), caso migliore $\Theta(n)$ (array ordinato), veloce su sequenze quasi ordinate.

Esempio. Con $n=5$ servono $4$ confronti su $[1,2,3,4,5]$ e $10$ su $[5,4,3,2,1]$ . Traccia su $S=[5,2,9,1,6]$ :

$i$	`curr`	prefisso ordinato prima	prefisso dopo	confronti
1	2	$[5]$	$[2,5]$	1 ( $5>2$ , poi si esce dall'array)
2	9	$[2,5]$	$[2,5,9]$	1 ( $5>9$ falso)
3	1	$[2,5,9]$	$[1,2,5,9]$	3 (tutti maggiori di $1$ )
4	6	$[1,2,5,9]$	$[1,2,5,6,9]$	2 ( $9>6$ vero, $5>6$ falso)

Totale $1+1+3+2=7$ confronti: tra il minimo $n-1=4$ e il massimo $\frac{n(n-1)}{2}=10$ . Ogni confronto vero sposta un elemento a destra e corrisponde a una inversione (coppia fuori ordine) risolta: qui le inversioni sono $(5,2),(5,1),(2,1),(9,1),(9,6)$ , cioè $5$ . A queste si aggiunge al più un confronto falso per iterazione, quello che ferma lo scorrimento (nelle iterazioni $i=2$ e $i=4$ ; nelle altre il ciclo finisce perché si esce dall'array): $5+2=7$ . In generale confronti $\le$ inversioni $+\,(n-1)$ , per questo un array quasi ordinato, con poche inversioni, costa poco.

Merge sort

Divide et impera: si divide in due metà, si ordinano ricorsivamente, si fondono le due sequenze ordinate con un solo passaggio.

Algoritmo mergeSort(S)
Input: sequenza S di n elementi      Output: S ordinata
if n <= 1 then return S
metà <- floor(n/2)
L <- mergeSort(S[0..metà-1]);  R <- mergeSort(S[metà..n-1])
return merge(L, R)

Formula (costo del merge sort). merge(L, R) confronta le due teste e sposta la minore nell'output: $\Theta(\lvert L \rvert + \lvert R \rvert)$ . Costo: l'albero della ricorsione ha $\lceil \log_2 n \rceil + 1$ livelli e al livello $i$ le $2^i$ chiamate lavorano su sequenze di taglia $\approx n/2^i$ , con costo totale per livello $\Theta(n)$ (il costo di un nodo è la fusione): $\Theta(n \log n)$ per ogni istanza. Richiede $\Theta(n)$ di spazio ausiliario. È stabile se in caso di parità si prende l'elemento di sinistra (verificato: per $n = 1024$ già ordinato i confronti sono $5120$ ).

Esempio. Per $n=8$ l'albero ha $\log_28+1=4$ livelli e nel caso pessimo i confronti sono $n\log_2n-n+1=17$ .

Come funziona merge. Si tengono due indici, uno per ogni sequenza ordinata; a ogni passo si confrontano le due teste e si copia la minore. Esempio con $L=[2,5,8]$ e $R=[1,6,7]$ : $2$ contro $1$ dà $1$ ; $2$ contro $6$ dà $2$ ; $5$ contro $6$ dà $5$ ; $8$ contro $6$ dà $6$ ; $8$ contro $7$ dà $7$ ; resta $8$ , copiato senza confronto: output $[1,2,5,6,7,8]$ con $5$ confronti, al più $|L|+|R|-1$ . Ogni confronto mette un elemento in output, quindi il costo è lineare.

Da dove viene $n\log_2n$ . Sia $T(n)$ il costo: due chiamate su metà dati più una fusione lineare, $T(n)=2T(n/2)+cn$ . Si "srotola": il livello $0$ ha $1$ fusione di taglia $n$ (costo $cn$ ), il livello $1$ ha $2$ fusioni di taglia $n/2$ (costo $2\cdot c\frac n2=cn$ ), il livello $i$ ha $2^i$ fusioni di taglia $n/2^i$ (costo $2^i\cdot c\frac{n}{2^i}=cn$ ). Ogni livello costa $cn$ e i livelli sono $\log_2n$ (la taglia si dimezza fino a $1$ : lo stesso conto della ricerca binaria, Problemi computazionali e algoritmi), quindi $T(n)=cn\log_2n+\Theta(n)$ . Traccia su $S=[5,2,9,1,6]$ : la ricorsione divide in $[5,2]$ e $[9,1,6]$ , poi $[9]$ e $[1,6]$ ; le fusioni sono $[5]+[2]\to[2,5]$ ( $1$ confronto), $[1]+[6]\to[1,6]$ ( $1$ ), $[9]+[1,6]\to[1,6,9]$ ( $2$ ), $[2,5]+[1,6,9]\to[1,2,5,6,9]$ ( $3$ ): totale $7$ confronti.

Quick sort

Si sceglie un pivot $p$ (ad esempio l'ultimo elemento), si partiziona in elementi $< p$ e $\ge p$ in loco con un passaggio, si mette il pivot al suo posto definitivo e si ordinano ricorsivamente le due parti.

Algoritmo quickSort(S, lo, hi)
if lo >= hi then return
p <- S[hi]; i <- lo
for j <- lo to hi-1 do
    if S[j] < p then swap(S[i], S[j]); i <- i + 1
swap(S[i], S[hi])
quickSort(S, lo, i-1); quickSort(S, i+1, hi)

Proprietà (costo del quick sort). $S[lo..i-1] < p \le S[i..j-1]$ . Costo: $\Theta(n)$ per partizione. Se il pivot divide in parti bilanciate l'albero ha altezza $\Theta(\log n)$ e il costo è $\Theta(n \log n)$ ; se è sempre il minimo o il massimo (array già ordinato con pivot ultimo) il costo è $\sum (n - i) = \Theta(n^2)$ . Con pivot scelto a caso il tempo atteso è $O(n \log n)$ : è l'esempio classico di caso pessimo patologico (vedi Complessità in tempo e caso pessimo). Spazio ausiliario $O(\log n)$ attesi (stack).

Esempio. Con pivot ultimo su un array già ordinato di $n=6$ elementi i confronti sono $5+4+3+2+1=15$ : $\Theta(n^2)$ . Il pivot è il massimo: tutti gli altri $n-1$ elementi vanno a sinistra, la parte destra è vuota e il problema scende solo di $1$ , quindi $T(n)=T(n-1)+n-1$ , che dà $\sum_{k=1}^{n-1}k=\frac{n(n-1)}{2}$ .

Traccia su $S=[5,2,9,1,6]$ con pivot ultimo: partizione con pivot $6$ : gli elementi $5,2,1$ sono $<6$ e passano a sinistra, $9$ resta a destra: $[5,2,1,6,9]$ , pivot in posizione $3$ ( $4$ confronti). Si ordina ricorsivamente $[5,2,1]$ : pivot $1$ , nessuno è minore, il pivot va in testa: $[1,2,5]$ ( $2$ confronti); poi $[2,5]$ : pivot $5$ , $2<5$ , già a posto ( $1$ confronto). Totale $4+2+1=7$ confronti; il lato destro $[9]$ ha un solo elemento (caso base). Con pivot a caso la probabilità che il pivot cada nel mezzo (tra $n/4$ e $3n/4$ ) è $\frac12$ , e un pivot "buono" riduce il problema ad almeno $\frac34$ : in media servono $O(\log n)$ livelli di partizione da $\Theta(n)$ ciascuno, il che dà il tempo atteso $O(n\log n)$ (media rispetto alla scelta casuale del pivot: Valore atteso).

Heap sort

Definizione (heap sort). Si costruisce uno heap sull'array e si estrae ripetutamente il massimo (heap sort con max-heap) mettendolo in fondo all'array: in loco.

bottom-up heap-construction: $\Theta(n)$ (vedi Costruzione di uno heap);

per $\text{end} = n-1$ fino a $1$ : scambia $S[0]$ con $S[\text{end}]$ e fai down-heap su $S[0..\text{end}-1]$ : $n-1$ passi da $O(\log n)$ .

Esempio. Per $n=1024$ : costruzione bottom-up $\Theta(n)$ e $1023$ down-heap da al più $\log_21024=10$ passi, circa $10^4$ operazioni. Perché l'ordine è crescente con un max-heap: il massimo in radice viene scambiato con l'ultima posizione utile dell'array, che è la sua posizione definitiva; poi la parte ancora da sistemare si accorcia di $1$ e un down-heap ripristina l'heap (Heap). L'array è così riempito dal fondo, dal massimo al minimo, e a fine algoritmo risulta crescente senza memoria aggiuntiva.

Totale $\Theta(n \log n)$ per ogni istanza e $O(1)$ di spazio ausiliario. Equivale all'ordinamento con coda con priorità su heap (vedi Heap).

Ordinare senza confrontare

Formula (ordinamento per conteggio). Se le chiavi sono interi in $[0, K]$ si può ordinare (o contare) in $\Theta(n + K)$ con un array di contatori $B[0..K]$ : una scansione che fa $B[S[i]] \leftarrow B[S[i]] + 1$ e una scansione di $B$ . Non usa confronti, quindi non è soggetto al limite sotto. Con $K = O(n)$ è lineare (si usa nell'esercizio della mediana di $n$ chiavi in $[0, 10n]$ ). L'array dei contatori è una mappa con chiavi intere (Mappe e dizionari, array di taglia $|U|$ ) e il costo $\Theta(n+K)$ è la somma dei due passaggi: $n$ incrementi e una scansione di $K+1$ contatori.

Esempio. Con $S=[3,1,3,0]$ e $K=3$ si ottiene $B=[1,1,0,2]$ e quindi l'ordine $0,1,3,3$ : $B[0]=1$ ( $0$ compare una volta), $B[1]=1$ , $B[2]=0$ , $B[3]=2$ ; leggendo $B$ da sinistra si scrive $0$ una volta, $1$ una volta, nessun $2$ , $3$ due volte.

Limite inferiore

Teorema (limite inferiore per l'ordinamento per confronti). Ogni algoritmo di ordinamento basato su confronti richiede $\Omega(n \log n)$ confronti al caso pessimo.

Esempio. Per $n=3$ ci sono $3!=6$ permutazioni, quindi servono almeno $\lceil\log_26\rceil=3$ confronti; per $n=1024$ almeno $\log_21024!\approx8769$ .

Dimostrazione. L'esecuzione su ogni istanza è descritta da un albero di decisione binario: ogni nodo interno è un confronto $S[i] < S[j]$ , ogni foglia una permutazione dell'input prodotta come risposta. Per essere corretto l'algoritmo deve poter produrre ognuna delle $n!$ permutazioni, quindi l'albero ha almeno $n!$ foglie. Un albero binario con $m$ foglie ha altezza $\ge \log_2 m$ (relazione $m \le 2^h$ , vedi Alberi binari), perciò l'altezza è $\ge \log_2 n!$ . Poiché $n! \ge (n/2)^{n/2}$ , $\log_2 n! \ge \frac n2 \log_2 \frac n2 \in \Omega(n \log n)$ . La disuguaglianza $n!\ge(n/2)^{n/2}$ si vede scrivendo $n!=n(n-1)\cdots1$ e tenendo solo i primi $n/2$ fattori $n,n-1,\dots,\frac n2+1$ , ciascuno $\ge\frac n2$ , scartando gli altri (tutti $\ge1$ ); si usa il fattoriale e il numero di permutazioni di $n$ oggetti (Fattoriale e coefficienti binomiali, Calcolo combinatorio per la probabilità). Poi $\log_2$ del prodotto è la somma dei logaritmi, $\log_2\big((n/2)^{n/2}\big)=\frac n2\log_2\frac n2$ (Esponenziale e logaritmo) e $\log_2\frac n2=\log_2n-1\in\Theta(\log n)$ . L'albero di decisione è un albero binario (proprio) e il legame tra foglie e altezza è la relazione $m\le2^h$ di Alberi binari. Con $n=3$ : $3!=6$ foglie, $h\ge\lceil\log_26\rceil=\lceil2{,}58\rceil=3$ . L'altezza dell'albero è il numero di confronti nel caso peggiore. $\square$

Quindi merge sort e heap sort sono ottimi (asintoticamente) tra gli algoritmi basati su confronti. Il grafico seguente confronta il limite inferiore $\log_2 n!$ (con l'approssimazione di Stirling $n\log_2 n-n\log_2e+\frac12\log_2(2\pi n)$ , accurata a meno di $0{,}02$ già da $n=8$ : $15{,}28$ contro $15{,}30$ ) con i confronti del merge sort: per $n=64$ il minimo teorico è $296$ e il merge sort ne fa al più $321$ , cioè solo l' $8\%$ in più.

Grafico interattivo: Limite inferiore log2(n!) per l'ordinamento per confronti (Stirling) e confronti del merge sort al caso pessimo n·log2 n − n + 1: a n = 64 sono 296 contro 321, quindi il merge sort è quasi ottimo

Grafico interattivo: Confronti al caso pessimo in funzione di n: selection sort e insertion sort fanno n(n−1)/2, il merge sort n·log₂n − n + 1 (esatto per n potenza di 2); a n = 64 sono 2016 contro 321, mentre l'insertion sort su un array già ordinato ne fa solo n − 1 = 63

Riepilogo

Algoritmo	Caso pessimo	Caso migliore	Spazio ausiliario	In loco
selection sort	$\Theta(n^2)$	$\Theta(n^2)$	$O(1)$	sì
insertion sort	$\Theta(n^2)$	$\Theta(n)$	$O(1)$	sì
merge sort	$\Theta(n \log n)$	$\Theta(n \log n)$	$\Theta(n)$	no
quick sort	$\Theta(n^2)$ (atteso $O(n \log n)$ )	$\Theta(n \log n)$	$O(\log n)$	sì
heap sort	$\Theta(n \log n)$	$\Theta(n \log n)$	$O(1)$	sì

Errori comuni

Dire che il quick sort è $\Theta(n \log n)$ al caso pessimo: lo è atteso (o con buon pivot); al caso pessimo è quadratico.
Confondere il caso pessimo con il caso migliore dell'insertion sort (lineare solo su array ordinato).
Dimenticare che l'invariante di selection sort riguarda anche i valori, non solo l'ordine: il prefisso contiene gli $i$ elementi più piccoli.
Applicare il limite $\Omega(n \log n)$ ad algoritmi che non usano confronti.

Versione ripasso

Problema: ordinare $S[0..n-1]$ con confronti ( $<$ , $\le$ , $=$ ); taglia $n$ (vedi Problemi computazionali e algoritmi). Esempio di riferimento $S=[5,2,9,1,6]$ , ordine finale $[1,2,5,6,9]$ .
Selection sort: per ogni $i$ si cerca il minimo di $S[i..n-1]$ e lo si scambia in posizione $i$ . Invariante: $S[0..i-1]$ contiene gli $i$ minimi, ordinati. Confronti $\frac{n(n-1)}{2}$ sempre, $\Theta(n^2)$ ; su $S$ sono $4+3+2+1=10$ (coda con priorità su lista non ordinata, vedi Code con priorità).
Insertion sort: invariante $S[0..i-1]$ ordinato; si inserisce $S[i]$ spostando a destra i maggiori. Pessimo $\Theta(n^2)$ (array decrescente), migliore $\Theta(n)$ (ordinato), veloce su sequenze quasi ordinate (vedi Complessità in tempo e caso pessimo). Confronti $\le$ inversioni $+ (n-1)$ : su $S$ sono $5$ inversioni e $7$ confronti.
Merge sort: se $n \le 1$ ritorna; altrimenti ordina ricorsivamente le metà $L$ e $R$ e restituisce merge(L, R). merge confronta le due teste e copia la minore, costo $\Theta(|L|+|R|)$ . Ricorrenza $T(n) = 2T(n/2) + cn$ : $\lceil\log_2 n\rceil+1$ livelli, costo $cn$ per livello, quindi $\Theta(n\log n)$ per ogni istanza; spazio $\Theta(n)$ . Su $S$ : $7$ confronti. Con $L=[2,5,8]$ e $R=[1,6,7]$ : $5$ confronti.
Quick sort: pivot $p = S[hi]$ ; partizione in loco con $S[lo..i-1] < p \le S[i..j-1]$ ; pivot in posizione $i$ ; ricorsione su $[lo, i-1]$ e $[i+1, hi]$ . Partizione $\Theta(n)$ ; pivot bilanciato $\Theta(n\log n)$ ; pessimo $\Theta(n^2)$ : array già ordinato con pivot ultimo dà $T(n) = T(n-1) + n - 1$ e $\frac{n(n-1)}{2}$ confronti. Con pivot casuale il tempo atteso è $O(n\log n)$ (vedi Valore atteso). Spazio $O(\log n)$ atteso. Su $S$ : $7$ confronti.
Heap sort: bottom-up $\Theta(n)$ (vedi Costruzione di uno heap), poi per $\text{end} = n-1$ fino a $1$ : scambia $S[0]$ con $S[\text{end}]$ e down-heap su $S[0..\text{end}-1]$ con max-heap. $\Theta(n\log n)$ , in loco, $O(1)$ di spazio (vedi Heap). Per $n=1024$ : $1023$ down-heap da al più $10$ passi.
Senza confronti: chiavi intere in $[0,K]$ : contatori $B[0..K]$ con $B[S[i]] \leftarrow B[S[i]] + 1$ e scansione di $B$ ; $\Theta(n+K)$ (vedi Mappe e dizionari). Esempio $S=[3,1,3,0]$ , $K=3$ : $B=[1,1,0,2]$ , ordine $0,1,3,3$ .
Limite inferiore: albero di decisione con almeno $n!$ foglie; altezza $\ge \log_2 n! \ge \frac n2 \log_2 \frac n2$ (relazione $m \le 2^h$ di Alberi binari), quindi $\Omega(n\log n)$ confronti nel caso pessimo. Per $n=3$ : $\lceil\log_2 6\rceil = 3$ . Merge sort e heap sort sono ottimi.
Riepilogo: caso pessimo selection $n^2$ , insertion $n^2$ , merge $n\log n$ , quick $n^2$ (atteso $n\log n$ ), heap $n\log n$ ; spazio ausiliario $O(1)$ , $O(1)$ , $\Theta(n)$ , $O(\log n)$ , $O(1)$ .
Traccia selection sort su $S$ : $i=0$ : minimo $1$ dalla posizione $3$ , array $[1,2,9,5,6]$ ; $i=1$ : $2$ già al suo posto; $i=2$ : minimo $5$ , array $[1,2,5,9,6]$ ; $i=3$ : minimo $6$ , array $[1,2,5,6,9]$ .
Traccia insertion sort su $S$ : il prefisso ordinato passa da $[5]$ a $[2,5]$ , $[2,5,9]$ , $[1,2,5,9]$ e infine $[1,2,5,6,9]$ , con $1+1+3+2=7$ confronti.
Traccia merge sort su $S$ : la ricorsione divide in $[5,2]$ e $[9,1,6]$ , poi in $[9]$ e $[1,6]$ . Le fusioni sono $[2,5]$ ( $1$ confronto), $[1,6]$ ( $1$ ), $[1,6,9]$ ( $2$ ) e $[1,2,5,6,9]$ ( $3$ ): totale $7$ .
Traccia quick sort su $S$ : pivot $6$ con partizione $[5,2,1,6,9]$ e pivot in posizione $3$ ( $4$ confronti); poi $[5,2,1]$ con pivot $1$ dà $[1,2,5]$ ( $2$ confronti) e $[2,5]$ dà $1$ confronto. Totale $7$ .
Caso migliore: quick sort con partizioni bilanciate, $\Theta(n\log n)$ ; è il caso di pivot vicino alla mediana.
Errori tipici: quick sort $\Theta(n\log n)$ nel caso pessimo; caso migliore e pessimo dell'insertion sort invertiti; limite $\Omega(n\log n)$ applicato ad algoritmi senza confronti.