L’ InsertionSort è uno degli algoritmi probabilmente più facili da capire che ci sono: esso si basa praticamente sullo stesso meccanismo che ci porta ad ordinare meccanicamente le carte mentre giochiamo.

InsertionSort, dall’ inglese ordinamento per inserimento, funziona infatti così:

Abbiamo un mazzo di carte non ordinato.
Peschiamo una carta e la teniamo in mano.
Peschiamo una seconda carta e facciamo il confronto: questa è maggiore o uguale alla carta che avevamo? > Maggiore, la mettiamo a destra, minore a sinistra.
Peschiamo una terza carta e la confrontiamo con le altre due e la inseriamo nel giusta posizione.
Ripetiamo con tutte le carte del mazzo, finchè non avremo in mano tutto il mazzo ordinato dalla carta più piccola alla carta più grande.

E’ effettivamente questo che fà l’ algoritmo di InsertionSort e per farlo, lo fà senza creare Array di supporto quindi In Place.

Lo spazio occupato infatti, è Theta(1).

Nei casi peggiori e medio, il tempo di esecuzione è di O(n^2) che è veramente inefficiente, ma si presta molto bene ad ordinare insiemi già quasi ordinati.

Esempio di esecuzione:

Vediamo un esempio con un array di numeri:

Array di Interi A: [1,4,5,3,2,]

Applichiamo l’algoritmo, di cui vedremo fra poco il codice, all’ array:

  1. [1, 4, 5, 3, 2] Seleziona il minimo e lo mette in prima posizione.
  2. [1, 2, 4, 5, 3] Cerca il secondo minimo (2) e lo mette in posizione A[1]
  3. [1, 2, 3, 4, 5] Cerca il terzo minimo (3) e lo mette nella posizione sucessiva A[2]
  4. [1, 2, 3, 4, 5] Cerca il quarto minimo (4) e lo mette nella posizione successiva A[3]
  5. [1, 2, 3, 4, 5] L’array è terminato, quindi ora è ordinato.

La parte in grassetto è quella ordinata ad ogni passo dell’ algoritmo. Ecco una gif con un esempio di esecuzione, preso da Wikipedia ma velocizzato un po’:

Pseudocodice dell’algoritmo Insertion Sort

Vediamo quindi uno pseudocodice dell’ algoritmo di ordinamento Insertion Sort:

for j=2 to array.length(): //scorro l'array per la sua lunghezza
 chiave = array[j]; //Prendo l'elemento j
 i=j-1; //Prendo il suo precedente
 while i>0 and A[i]>chiave //se il suo precedente è maggiore
     A[i+1]=A[i] //Scambio il successivo col precedente
     i=j-1 //Lo faccio per tutti i precedenti
     A[i+1] = chiave

Un’altra caratteristica è la facilità di implementazione in praticamente qualsiasi linguaggio, richiedendo solamente l’array di input.

Codice dell’algoritmo Insertion Sort in Python3

Ecco una possibile implementazione dello pseudocodice, utilizzando python:


def insertionSort(arr):
    for i in range(1, len(arr)):
        val = arr[i]
        j = i-1
        while j >= 0 and arr[j] > val:
            arr[j+1] = arr[j]
            j = j -1
        arr[j+1] = val
    return arr

import unittest
import random

class SortingTest(unittest.TestCase):
    def setUp(self):
        self.i = list(range(0, 100))
        self.sort = insertionSort

    def testOrdered(self):
        self.assertEqual(self.i, self.sort(self.i))

    def testReversed(self):
        self.assertEqual(self.i, self.sort(self.i[::-1]))

    def testUnordered(self):
        self.assertEquals(self.i, self.sort(random.sample(self.i, len(self.i))))

if __name__ == "__main__":
    unittest.main()