L’Insertion Sort é un’altro noto e semplice algoritmo di ordinamento che si basa sul concetto di ordinamento per inserzione, simile al modo in cui un essere umano, spesso, ordina un mazzo di carte.
Vediamo nel dettaglio: dato un vettore di n elementi, vengono effettuate n-1 iterazioni ed a ogni iterazione i, si scandisce una porzione del vettore cha va da i-1 a 0 trovando la posizione giusta dell’i-esimo elemento, tramite una serie di scambi.
Quindi procedendo in questo modo la porzione del vettore che va da i-1 a 0 risulterá sempre ordinata e alla fine di n iterazioni tutto il vettore risulterá ordinato.
Vediamo l’implementazione dell’algoritmo Insertion Sort in Java:
public void insertionSort(int [] array) {
for(int i = 1; i < array.length; i++) {
int x = i;
int j = i-1;
for(; j >= min; j--) {
//Scambiamo l'elemento in posizione x fino a quando non raggiunge
//la posizione corretta nel sotto-vettore, cioé quando
//non é verificata piú questa condizione
if(array[j]>array[x]) {
int k = array[x];
array[x] = array[j];
array[j] = k;
x = j; //La sua nuova posizione nel sotto-vettore
} else break; //Significa che l'i-esimo elemento è nella sua giusta posizione
//quindi possiamo terminare l' iterazione
}
}
}La complessitá dell’ algoritmo sia in numero di confronti che di scambi é quadratica nel caso peggiore e medio O(n^2), mentre risulta lineare O(n) nel caso migliore (quando il vettore risulta parzialmente ordinato).
Esso ha un buon comportamento per vettori di piccole dimensioni, infatti viene abbinato con gli algoritmi di tipo (come vedremo) Divide et Impera quali il Merge Sort e Quick Sort.
