Il metodo di ordinamento ad inserzione trae lo spunto dall'idea che un vettore ordinato
si ottiene inserendo le sue componenti una per una "al posto giusto".
In questo algoritmo non si introduce un secondo vettore, ma
si "simula" l' inserzione degli elementi nel vettore dato (in
place).
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.
Esempio
Supponiamo che l’array inizialmente contenga i valori 4 3 1
2 in questa sequenza.
|
|
4 |
---> |
4 |
---> |
|
---> |
3 |
|
(a) ---> |
3 |
|
|
|
4 |
|
4 |
|
|
1 |
|
1 |
|
1 |
|
1 |
|
|
2 |
|
2 |
|
2 |
|
2 |
In figura (a), estraiamo 3.
Poi spostiamo gli elementi precedenti (in questo caso 4) verso destra fino a
trovare il posto giusto per inserire il 3.
|
|
3 |
---> |
3 |
---> |
|
---> |
1 |
|
|
4 |
|
4 |
|
3 |
|
3 |
|
(b)---> |
1 |
|
|
|
4 |
|
4 |
|
|
2 |
|
2 |
|
2 |
|
2 |
In figura b) si ripete lo stesso processo di
figura per il valore 1 in posizione 3.
In questo caso spostiamo sia 3 che 4 di una posizione verso destra.
|
|
1 |
---> |
1 |
---> |
1 |
---> |
1 |
|
|
3 |
|
3 |
|
|
|
2 |
|
|
4 |
|
4 |
|
3 |
|
3 |
|
(c)---> |
2 |
|
|
|
4 |
|
4 |
In figura c) completiamo l'ordinamento
inserendo il 2 nel posto giusto e spostando nuovamente 3 e 4 di una posizione verso
destra.