Insertion Sort

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' algoritmo :
    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.

Questa é l' applet che ci mostra l' esecuzione dell' Insertion Sort :

Per potere utilizzare questo tool necessaria l' installazione della Java Virtual Machine.
Scarica la Java Virtual Machine

Inserite manualmente i numeri nelle caselle, oppure usate la generazione automatica, con gli opportuni pulsanti : Random (casuale), Crescente e Descrescente. Per far partire l' ordinamente usate il pulsante Ordina e regolate la velocita con l' apposita slider.