Algoritmi di ordinamento

Problema. Input: sequenza $S[0..n-1]$ di chiavi confrontabili. Output: gli stessi elementi in ordine crescente (vedi Problemi computazionali e algoritmiProblema computazionale come insieme di coppie (istanza, soluzione); algoritmo e modello di calcolo RAM; pseudocodice; taglia di un'istanza; ADT e struttura dati concreta; esempio svolto con ricerca lineare e binaria in un array ordinato.Problemi computazionali e algoritmi →). La taglia è $n$. Qui si studiano algoritmi basati su confronti (le chiavi si usano solo con $<$, $\le$, $=$).

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])

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àEntry chiave-valore; ADT coda con priorità (insert, min, removeMin) con chiave minima = priorità massima; esempio di esecuzione; applicazioni; implementazioni con lista non ordinata e ordinata e relativi costi; ordinamento tramite coda con priorità.Code con priorità →).

Insertion sort

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 pessimoPerché lo studio sperimentale non basta; complessità al caso pessimo come massimo sul numero di operazioni tra le istanze di una data taglia; stima con limiti superiore e inferiore senza trovare l'istanza peggiore; esempi arrayMax, prefixAverages e InsertionSort; efficienza asintotica e limiti dell'analisi.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.

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)

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$).

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)

Invariante del ciclo di partizione: $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 pessimoPerché lo studio sperimentale non basta; complessità al caso pessimo come massimo sul numero di operazioni tra le istanze di una data taglia; stima con limiti superiore e inferiore senza trovare l'istanza peggiore; esempi arrayMax, prefixAverages e InsertionSort; efficienza asintotica e limiti dell'analisi.Complessità in tempo e caso pessimo →). Spazio ausiliario $O(\log n)$ attesi (stack).

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.

1. bottom-up heap-construction: $\Theta(n)$ (vedi Costruzione di uno heapCostruire uno heap da un array di n entry: approccio top-down con n-1 insert, Theta(n log n); approccio bottom-up con down-heap dalle foglie verso la radice, Theta(n), con dimostrazione della somma; esempi svolti, in loco; unione di due alberi con heap-order.Costruzione di uno heap →);
2. 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)$.

Totale $\Theta(n \log n)$ per ogni istanza e $O(1)$ di spazio ausiliario. Equivale all'ordinamento con coda con priorità su heap (vedi HeapAlbero binario completo e sua altezza floor(log2 n); heap = albero completo con heap-order property; proprietà (radice minima, cammini non decrescenti); rappresentazione su array con level numbering; insert con up-heap bubbling, removeMin con down-heap bubbling, rimozione di una entry qualsiasi; invarianti e costi Theta(log n); esempio svolto.Heap →).

Ordinare senza confrontare

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]$).

Limite inferiore

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

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 binariAlbero binario e albero binario proprio; interfaccia; relazioni tra nodi, foglie e altezza (m = n-m+1, h+1 <= m <= 2^h, 2h+1 <= n <= 2^(h+1)-1) con dimostrazioni; visita inorder; parse tree e valutazione di espressioni; heightSum come esempio di calcolo di un'informazione più ricca.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)$. 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.

Riepilogo

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.