# Algoritmi/Gli algoritmi di ordinamento

Algoritmi
Copertina Tutti i moduli · Sviluppo
    CopertinaAlgoritmi/Copertina
* Gli algoritmiAlgoritmi/Gli algoritmi
* L'analisi di complessità degli algoritmiAlgoritmi/L'analisi di complessità degli algoritmi
* Gli algoritmi di ordinamentoAlgoritmi/Gli algoritmi di ordinamento
* Grafi e alberiAlgoritmi/Grafi e alberi
* La ricorsioneAlgoritmi/La ricorsione
* Il paradigma "divide et impera"Algoritmi/Il paradigma "divide et impera"
* Gli heapAlgoritmi/Gli heap
* Le tabelle di simboliAlgoritmi/Le tabelle di simboli
* Alberi binari di ricerca (BST)Algoritmi/Alberi binari di ricerca (BST)
* Tipologie di problemiAlgoritmi/Tipologie di problemi
* Le tabelle di hashAlgoritmi/Le tabelle di hash
* L'ADT grafo non orientatoAlgoritmi/L'ADT grafo non orientato
* Gli algoritmi di visita dei grafiAlgoritmi/Gli algoritmi di visita dei grafi
* Le applicazioni degli algoritmi di visita dei grafiAlgoritmi/Le applicazioni degli algoritmi di visita dei grafi
* Gli alberi ricoprenti minimiAlgoritmi/Gli alberi ricoprenti minimi
* I cammini minimiAlgoritmi/I cammini minimi
Modifica il sommario
* 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).

## 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

Osservazioni:
* 3! permutazioni possibili
* 3 confronti nel caso peggiore
Caso di n interi :
| livello i | numero di foglie 2$^i$ |
| 0 | 1 = 2$^0$ |
| 1 | 2 = 2$^1$ |
| 2 | 4 = 2$^2$ |
* 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 riempie 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

* ↑ La base del logaritmo scompare perché si sottointende la moltiplicazione per una costante per il cambio di base.