Insertion sort: differenze tra le versioni

Contenuto cancellato Contenuto aggiunto
Botcrux (discussione | contributi)
m →‎Descrizione dell'algoritmo: Bot: Fix dimensionamento immagini (v. richiesta)
Riga 15:
L'algoritmo solitamente ordina la sequenza sul posto. Si assume che la sequenza da ordinare sia partizionata in una sottosequenza già ordinata, all'inizio composta da un solo elemento, e una ancora da ordinare. Alla <math>k</math>-esima iterazione, la sequenza già ordinata contiene <math>k</math> elementi. In ogni iterazione, viene rimosso un elemento dalla sottosequenza non ordinata (scelto, in generale, arbitrariamente) e ''inserito'' (da cui il nome dell'algoritmo) nella posizione corretta della sottosequenza ordinata, estendendola così di un elemento.
 
[[File:AnimazioneInsertionSort.gif|left|thumb|492pxupright=2.2|Simulazione dell'insertion sort su di un array]]
 
Per fare questo, un'implementazione tipica dell'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.