L'algoritmo insertion sort
L'insertion sort è un algoritmo di ordinamento di un array (vettore) tra i più semplici da realizzare.
Lo pseudocodice
- for j=2 to n
- elemento = Array( j )
- i=j-1
- while i > 0 and Array( i ) > elemento
- Array( i+1 ) = Array ( i )
- i = i-1
- Array ( i+1 ) = elemento
L'algoritmo riceve in input un array non ordinato.
Elabora e restituisce in output l'array ordinato in modo crescente.
Come funziona l'algoritmo
La struttura ciclica for inizia le iterazioni dal secondo elemento in poi.
Per ciascun j-esimo elemento l'algoritmo lo confronta con gli elementi precedenti tramite una struttura ciclica condizionata while più interna.
- Se trova un elemento più grande lo sposta in avanti.
- Se trova un elemento minore o uguale termina il ciclo più interno (while).
L'algoritmo cessa l'esecuzione quando termina il ciclo più esterno (for)
Un esempio pratico
Considero un vettore con n=5 elementi
6 5 3 4 1
Per semplicità l'indice dell'array comincia con la posizione 1.
Nota. In molti linguaggi di programmazione il primo elemento di un array comincia dalla posizione 0. E' importante ricordarlo.
Iterazione 1 (j=2)
L'algoritmo confronta l'elemento in seconda posizione (5) con gli elementi precedenti.
6 5 3 4 1
Cinque è minore di sei. Quindi, 5 prende il posto di 6 e viceversa.
5 6 3 4 1
Iterazione 2 (j=3)
L'algoritmo confronta l'elemento in terza posizione (3) con gli elementi precedenti.
5 6 3 4 1
Tre è minore di 6. Quindi, 3 prende il posto di 6 e viceversa.
5 3 6 4 1
Tre è minore di 5. Quindi, 3 prende il posto di 5 e viceversa.
3 5 6 4 1
Iterazione 3 (j=4)
L'algoritmo confronta l'elemento in quarta posizione (4) con gli elementi precedenti.
3 5 6 4 1
Quattro è minore di 6. Quindi, 4 prende il posto di 6 e viceversa.
3 5 4 6 1
Quattro è minore di 5. Quindi, 4 prende il posto di 5 e viceversa.
3 4 5 6 1
Iterazione 4 (j=5)
L'algoritmo confronta l'elemento in quinta posizione (1) con gli elementi precedenti.
3 4 5 6 1
Uno è minore di 6. Quindi, 1 prende il posto di 6 e viceversa.
3 4 5 1 6
Uno è minore di 5. Quindi, 1 prende il posto di 5 e viceversa.
3 4 1 5 6
Uno è minore di 4. Quindi, 1 prende il posto di 4 e viceversa.
3 1 4 5 6
Uno è minore di 3. Quindi, 1 prende il posto di 3 e viceversa.
1 3 4 5 6
Ora l'array è ordinato.
E così via
