Implementazioni di algoritmi/Insertion sort: differenze tra le versioni

Jump to navigation Jump to search
nessun oggetto della modifica
Nessun oggetto della modifica
L''''Insertion sort''', in italiano '''ordinamento a inserimento''', è un [[algoritmo]] relativamente semplice per ordinare un [[array]]. Esso è un [[Algoritmo in loco|algoritmo ''in place'']], cioè ordina l'array senza doverne creare un altro “di appoggio”, quindi risparmia memoria.
 
Non è molto diverso dal modo in cui un essere umano, spesso, ordina un mazzo di carte. L'algoritmo utilizza due indici: il primo punta inizialmente al secondo elemento dell'array, il secondo inizia dal primo. Se il primo elemento è maggiore del secondo, i due valori vengono scambiati. Poi il primo indice avanza di una posizione e il secondo indice riparte sempredall'elemento precedente quello puntato dal primo elemento. Se ill'elemento primopuntato elementodal secondo indice non è maggiore di quello a cui punta il primo indice, il secondo indice avanza; e così fa, finché si trova nel punto in cui il valore del primo indice deve essere ''inserito'' (da qui ''insertion'').
L'algoritmo così tende a spostare man mano gli elementi maggiori verso destra.
 
0

contributi

Menu di navigazione