[:it]
Roma – 2 giugno 2018 Festa della Repubblica
Questo ordinamento è chiamato in inglese (insert-sort). Si basa sul meccanismo naturale che si attiva quando si inseriscono nuovi elementi in un elenco già ordinato: per esempio, supponiamo di avere una libreria con una collezione di giornalini o fumetti aventi sulla costa il numero progressivo dell’album e di voler inserire nuovi volumi, oppure di giocare a carte, ricevere dal mazziere una carta alla volta e volerla collocare nella giusta posizione della “mano”. In entrambi i casi possiamo individuare il medesimo algoritmo risolutivo.
Per ogni elemento dovremo quindi:
- individuare la posizione che deve occupare rispetto a quelli già presenti;
- predisporre un posto libero per poterlo inserire;
- effettuare l’inserimento.
Ad esempio devo inserire i seguenti numeri:
20 33 17 8 13 40 2 37
inserisco il 20
poi inserisco il 33 che trova collocazione dopo il 20
in questo caso l’inserimento non ha richiesto alcuna operazione preventiva.
inserisco il 17, deve essere inserito prima di tutti gli altri, quindi è necessario effettuare lo spostamento a destra di una posizione di tutti gli elementi inseriti per creare un buco:
17 20 33
per il numero 8 si procede come il numero 17.
per il numero 13 è necessario predisporre uno spazio intermedio tra l’8 e il 17 e quindi effettuare l’inserimento.
8 13 17 20 33
per il numero 40 non si richiede spostamenti perchè è il numero più grande.
8 13 17 20 33 40
il 2 richiede invece lo spostamento di tutti gli altri valori:
2 8 13 17 20 33 40.
Infine il 37 si posiziona prima del 40, ottenendo così il vettore ordinato:
2 8 13 17 20 33 37 40
ecco il riassunto di ciò che è avvenutoo
20
20 33
17 20 33
8 17 20 33
8 13 17 20 33 40
2 8 13 17 20 33 40
2 8 13 17 20 33 37 40
ecco l’algoritmo usato:
- confrontare l’elemento da inserire con quello presente in ultima posizione
- cominciare a spostare gli elementi verso destra finchè non si trova la posizione in cui inserire il nuovo elemento: in tal modo viene creato un buco che viene spostato da destra a sinistra fini a raggiunger la posizione corretta
- inserire il nuovo elemento in quella posizione.
[:]