Integer sort
Da Wikipedia, l'enciclopedia libera.
L'Integer Sort ( o Integersort ) è un algoritmo di ordinamento lineare, infatti la sua complessità, per particolari configurazioni del vettore da ordinare, è O(n). Questo algoritmo viene utilizzato infatti per ordinare un insieme finito di N elementi i cui valori sono compresi nell'intervallo chiuso (1,k); per fare questo l'Integer Sort fa uso di una struttura ausiliaria, un vettore di dimensione k, utilizzata per salvare il numero di occorrenze di ogni singolo elemento nel vettore da ordinare.
Indice |
[modifica] Spiegazione Astratta
L'algoritmo come detto in precedenza usa un vettore ausiliario( da ora in poi Y) dove la t-esima cella contiene la frequenza dell'elemento t nel vettore di input ( da ora in poi X). Per fare un esempio, se X fosse cosi strutturato:
posizione 1 2 3 4 5 6 7 8 9 elemento 10 2 8 3 2 4 4 1 5
Y sarebbe:
posizione 1 2 3 4 5 6 7 8 9 10 elemento 1 2 1 2 1 0 0 1 0 1
Una volta costruito Y con le frequenze di ogni elemento di X si può ricostruire il vettore ordinato, analizzando Y dalla prima cella:
- Se Y[k]=0 passa alla cella successiva di Y.
- Se Y[k]=c>0 aggiungi c volte il valore k in X.
[modifica] Pseudo-codice
IntegerSort(array X, intero K)
sia Y un array di dimensione k //Dichiarazione della struttura di appoggio
for i ← 1 to k do
Y[i] ← 0 //Inizializzazione del vettore Y
for i ← 1 to n do
Y[X[i]] ← Y[X[i]] + 1 //Costruzione del vettore delle frequenze
j ← 1
for i ← 1 to k do
while ( Y[i] > 0 ) do //Ricostruzione del vettore di X
X[j] ← i //sulla base di Y
j ← j + 1
Y[i] ← Y[i] - 1
[modifica] Analisi dell'algoritmo
La complessità dell'Integer Sort è O(N + k) infatti infatti la complessità per inizializzare il vettore e leggerlo per ricostruire X è O(k), mentre la complessità del terzo ciclo for è O(n). Da questo possiamo capire l'utilità dell Integer Sort: infatti se k = O(N) allora la complessità totale dell'algoritmo è O(n).
[modifica] Varianti
Esiste una generalizzazione dell'Integer Sort in grado di ordinare un insieme N di record, le cui chiavi sono comprese nell'intervallo (1,k). Esso è il Bucket Sort.
[modifica] Nota
Questo algoritmo è il bucket sort.
| Algoritmi di ordinamento | ||
|---|---|---|
| Teoria | Teoria della complessità computazionale | Notazione O Grande | Lista | Stack | Coda |  |
| Algoritmi a scambio | Bubble sort | Cocktail sort | Comb sort | Gnome sort | Quicksort | |
| Algoritmi di selezione | Selection sort | Heapsort | Smoothsort | |
| Algoritmi ad inserimento | Insertion sort | Shell sort | Tree sort | Library sort | Patience sorting | |
| Algoritmi a fusione | Merge sort | |
| Algoritmi non comparativi | Radix sort | Bucket sort | Counting sort | Pigeonhole sort | |
| Altri algoritmi | Stupid sort | |
