Insertion sort

Da Wikipedia, l'enciclopedia libera.

L'Insertion sort, in italiano ordinamento a inserimento, è un algoritmo relativamente semplice per ordinare un array. Non è molto diverso dal modo in cui un essere umano, spesso, ordina un mazzo di carte. Esso è un algoritmo in place, cioè ordina l'array senza doverne creare una copia, risparmiando memoria.

[modifica] Descrizione dell'algoritmo

L'algoritmo utilizza due indici: uno punta all'elemento da ordinare e l'altro all'elemento immediatamente precedente. Se l'elemento puntato dal secondo indice è maggiore di quello a cui punta il primo indice, i due elementi vengono scambiati di posto; altrimenti il primo indice avanza. Il procedimento è ripetuto finché si trova nel punto in cui il valore del primo indice deve essere inserito (da qui insertion).

Il primo indice punta inizialmente al secondo elemento dell'array, il secondo inizia dal primo. L'algoritmo così tende a spostare man mano gli elementi maggiori verso destra.

[modifica] Complessità

Pur avendo complessità quadratica, per array piccoli è solitamente l'algoritmo di ordinamento più veloce. Un algoritmo simile all'Insertion Sort ma dalla complessità minore è lo Shell sort. Tuttavia, anche lo shell sort non è in grado di competere con la combinazione dell'insertion sort con un algoritmo di tipo divide et impera, quale il quick sort o il merge sort.

[modifica] Pseudocodice

Segue lo pseudocodice per l'algoritmo.

insertion_sort(x[], n) 
    for i ← 1 to n - 1 do
        app ← x[i]       
        j ← i - 1
        while (j >= 0) and (x[j] > app) do
            x[j + 1] ← x[j]
            j ← j - 1 
        x[j + 1] ← app

Segue lo pseudocodice per linguaggi funzionali.

 insert :: Ord a => a -> [a] -> [a]
 insert item []  = [item]
 insert item (h:t) | item <= h = item:h:t
                   | otherwise = h:(insert item t)

 insertsort :: Ord a => [a] -> [a]
 insertsort []    = []   
 insertsort (h:t) = insert h (insertsort t)

[modifica] Bibliografia

Thomas Cormen; Charles E. Leiserson, Ronald Rivest. Introduction in Introduction to Algorithms . 20^a ed. Cambridge, Massachussetts, The MIT Press, 1998 .