Follow

Come ordina l'insertion sort.

Volevo discutere in qualche articolo alcuni problemi di algoritmica presentando alcuni algoritmi che li risolvono e analizzandone la complessità.

Cominciamo questa vetrina di algoritmi con quelli che risolvono il più classico dei problemi: l’ordinamento.

In particolare cominceremo vedendo uno dei più semplici: insertion sort.Insertion Sort :

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

L’algoritmo segue un procedimento molto semplice. Insertion Sort utilizza due indici: uno che punta all’elemento da ordinare (i) mentre l’altro comincia dall’elemento che precede il primo indice e va decrescendo (j). All’inizio viene messo in app il valore puntato dal primo indice. Se l’elemento puntato dal secondo indice è maggiore di app i due elementi vengono scambiati di posto e decrementato j, altrimenti il valore di app viene copiato in j, il primo indice viene incrementato di uno e infine j resettato.

Vediamo un esempio, supponiamo un array di prova:

5 3 7 2 8 4

All’inizio avremo i due indici cosi inizializzati:

j5 i3 2 8 4 app=3

ed eseguiremo i seguenti passi:

j3 i5 2 8 4 app=3
3 j5 i2 8 4 app=2
3j 2 i5 8 4 app=2
2 3 j5 i8 4 app=8
2 3 5 j8 i4 app=4
2 3 j5 4 i8 app=4
2 j3 4 5 i8 app=4

2 3 4 5 8

In pretica il meccanismo alla base dell’insertion sort è quello di selezionare un elemento con i ed andarlo ad inserire nel suo posto facendolo spostare piano piano verso sinistra.

Ma quanto è oneroso computazionalmente questo algoritmo? Nel caso migliore app è sempre minore dell’elemento puntato da j e quindi banalmente l’algorimto termina dopo aver scandito ogni casella dell’array.

Ma l’analisi dei costi va fatta analizzando caso peggiore (e spesso il caso medio). Nell’insertion sort il caso peggiore equivale a quando j deve scandire tutto il sotto-array dall’inizio alla fine, ovvero quando l’array è ordinato al contrario. In questo caso al primo ciclo avremo che j farà 1 passo, al secondo ciclo ne farà 2 e così via.

Questo ci dice che in un array di dimensione n avremo che j farà in totale:

1 + 2 + ... (n-1)

Che in forma chiusa equivale a:

n(n-1) / 2

Ovvero, per n che tende a infinito, j fa un numero di iterazione che cresce come una funzione quadratica: ovvero l’algoritmo ha complessità O(N²).

Ma quantifichiamo questa cosa in termini pratici. Prendiamo il nostro calcolatore ideale di esempio e supponiamo di aver un calcolatore che esegua (molto ottimisticamente) ogni iterazione in 1 nanosecondo e supponiamo di voler ordinare un array X di 40MB di interi. 40MB di interi, poichè ogni intero è composto da 4 byte, equivale ad un array con 40.000.000 / 4 elementi. Ovvero n = 10.000.000.

Poichè insertion sort ha complessità quadratica per ordinare X eseguirà 10^14 iterazioni (sono centomila miliardi di iterazioni). Poichè ogni operazione è eseguita in un nanosecondo il nostro calcolatore è in grado di fare 10^9 operazioni al secondo (un miliardo di operazioni al secondo). Quindi per ordinare l’array impiegherà 10^5 secondi = 100.000 secondi = 27.7 ore che è circa un giorno.

Poichè, invece, nel caso migliore abbiamo che il costo è lineare, nel caso migliore il nostro calcolatore impiegherà 10^-2 secondi ovvero un centesimo di secondo.

Quindi un applicazione che utilizza insertion sort, su grandi moli di dati ha un gap di complessità di 10^5/10^-2 = 10^7!! Ovvero il tempo che impiega la vostra applicazione può variare da pochi centesimi di secondo ad un giorno solo a causa di un input!!!

Decisamente inaccettabile per qualunque applicazione rispettabile. L’insertion sort è quindi grosso modo bocciato: è da tener presente però che può trovare validità per ordinare quantità piccole di dati soprattutto grazie alla sua capacità di essere in place, ovvero di non richiedere più memoria di quella dell’array dato in input.

Nel prossimo articolo continueremo la ricerca del miglior algoritmo di ordinamento, proveremo con il Selection Sort.