Algoritmi e programmazione:Gli algoritmi di ordinamento

Il titolo di questa voce non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è 3. Gli algoritmi di ordinamento.

2. L'analisi di complessità degli algoritmi	Algoritmi e programmazione	4. Grafi e alberi

Gli appunti che seguono sono contenuti nella sottopagina /sub (modifica · cronologia · aggiorna)

• 2 ordinamento interno: dati memorizzati in memoria centrale (accesso diretto ai dati → si ottimizza il numero di passi);
• ordinamento esterno: dati memorizzati in memoria di massa (tempi di attesa più lunghi → si ottimizza il numero di accessi).

• 3 ordinamento in loco: usa oltre al vettore da ordinare una quantità di memoria ausiliaria che non dipende dal numero di dati da ordinare.

• ordinamento stabile: l'ordine degli elementi ripetuti eventuali è uguale tra input e output.

Classificazione per complessità

• $O \left( n^2 \right)$ (quadratico): semplici, iterativi, basati sul confronto (es. insertion sort, selection sort, bubble sort);
• $O\left(n \sqrt n \right)$ (es. shell sort);
• $O\left(n \cdot \log{n} \right)$ (linearitmico): ottimi ma più complessi perché ricorsivi (es. merge sort, quick sort, heap sort);
• $O\left(n\right)$ (lineare): basati sul calcolo, ma ipotesi restrittive sui dati, cioè possono essere usati solo con determinati dati (es. counting sort).

Limite inferiore della complessità asintotica nel caso peggiore per gli algoritmi di ordinamento basati sul confronto

Gli algoritmi basati sul confronto non possono avere una complessità inferiore a $n \log{n}$ (linearitmica), solo quelli basati sul calcolo:

$T\left(n\right) = \Omega \left( n \cdot \log{n} \right)$

Dimostrazione

Caso di 3 interi (a₁, a₂, a₃).

Osservazioni:

• 3! permutazioni possibili
• 3 confronti nel caso peggiore

---

Caso di n interi

livello i	numero di foglie 2i
0	1 = 20
1	2 = 21
2	4 = 22

• osservazione: n! permutazioni possibili ≤ numero di foglie;
• servono almeno $2^h$ foglie per accomodare tutte le $n!$ permutazioni possibili → $2^h \geq n!$;
• tramite la relazione di Stirling $n! > {\left( {n \over e} \right)}^n$:

  $2^h > {\left( {n \over e} \right)}^n; \; \log_2{2^h} > \log{{\left( {n \over e} \right)}^n}; \; h > n \left( \log_2{n} - \log_2{e} \right) \Rightarrow T \left( n \right) = \Omega \left( n \log{n} \right) \quad n \rightarrow + \infty$

Bubble sort (o exchange sort)

Al 1° ciclo, confronta due elementi adiacenti, se necessario li scambia, quindi passa alla casella successiva → si ottiene solo che l'ultimo elemento a destra è il massimo, ma gli altri non sono ordinati, cioè il valore massimo è galleggiato a destra.

Il vettore si divide idealmente in due sottovettori → serve un doppio ciclo annidato:

• sottovettore destro: inizialmente vuoto, contiene via via i massimi ordinati;
• sottovettore sinistro: si svuota man mano.

Ottimizzazione: è possibile usare un flag per terminare prima il ciclo se non è stato effettuato alcuno scambio nel ciclo interno.

Selection sort

Al 1° ciclo, scandisce il vettore, trova la posizione del minimo, e lo scambia con il 1° elemento. Pertanto è il sottovettore sinistro che si riempe in modo ordinato, man mano che il ciclo viene incrementato → il selection sort e il bubble sort sono degli algoritmi incrementali. Il ciclo interno cerca il minimo nel sottovettore destro.

Counting sort

È un algoritmo stabile (va bene per le chiavi ripetute), ma non è un algoritmo in loco. Va a calcolare direttamente la posizione finale di un dato.

L'algoritmo crea il vettore delle occorrenze semplici, che contiene il numero di occorrenze nell'input del dato che corrisponde all'indice, e poi crea il vettore delle occorrenze multiple:

Leggendo il vettore in input da destra verso sinistra, pone ogni elemento nella posizione memorizzata nel vettore delle occorrenze multiple, quindi decrementa il valore posizione:

Utilizza 3 vettori: il vettore di partenza, il vettore risultato, e il vettore delle occorrenze. La dimensione del vettore delle occorrenze dipende dall'intervallo a cui possono appartenere i dati → non è un ordinamento in loco.

Viene implementato con 4 cicli for → $T\left(n\right) = O\left( n + k \right)$: si considera non più solo la dimensione dei dati, ma anche la loro complessità k, che cresce linearmente con n, ma la complessità k non può tendere a infinito. Supponendo k ∼ n: $T\left(n\right) = O\left(n\right)$.

Note

2. L'analisi di complessità degli algoritmi	Algoritmi e programmazione	4. Grafi e alberi