Insertion sort: differenze tra le versioni

{{Algoritmo

}}

 

 

== Descrizione dell'algoritmo ==

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.