Insertion sort: differenze tra le versioni

Versione delle 17:48, 13 set 2023

Versione attuale delle 09:32, 25 feb 2025

(9 versioni intermedie di 8 utenti non mostrate)

Riga 1:

{{Algoritmo

|classe = [[Algoritmo di ordinamento]]

|immagine = InsertionSorting insertion sort animationanim.gif

|didascalia = Esempio di ordinamento di una lista di numeri casuali.

|struttura dati = [[Array]]

Riga 13:

[[File:Insertion-sort-example-300px.gif|upright=1.4|thumb|Esempio grafico dell'insertion sort.]]

L{{'}}'''Insertion sort''', in italiano '''ordinamento a inserimento''', è un [[algoritmo]] relativamente semplice per [[Algoritmo di ordinamento|ordinare]] un [[array]]. Non è molto diverso dal modo in cui un essere umano, spesso, ordina un mazzo di carte. Esso è un [[Algoritmo in loco|algoritmo ''in place'']], cioè ordina l'array senza doverne creare una copia, risparmiando memoria. Pur essendo molto meno efficiente di algoritmi più avanzati, può avere alcuni vantaggi: ad esempio, è semplice da implementare ed è efficiente per insiemi di partenza che sono quasi ordinati.

== 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.

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 è minoremaggiore 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.

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.

Riga 24:

Seguono gli [[pseudocodice|pseudocodici]] per diversi algoritmi dell'insertion sort. Si assume che la numerazione degli elementi negli array inizi da 0.

=== [[Algoritmo iterativo]] ===

'''function''' insertionSortIterativo(array A)

Riga 35:

A[j+1] ← value;

=== [[Algoritmo ricorsivo]] ===

Per ordinare un array di dimensione ''n'', ''A[0..n-1]'', si ordina prima il sotto-array ''A[0..n-2]'' e poi si inserisce l<nowiki>{{'</nowiki>}}''n-1''-esimo elemento.

Il sotto-array di un elemento (''n==1'') è già ordinato.

Riga 49:

A[j+1] ← value

===Algoritmo per [[Programmazione funzionale|linguaggi funzionali]]===

insert :: Ord a => a -> [a] -> [a]