Insertion sort: differenze tra le versioni

Versione delle 17:50, 13 set 2023

Versione delle 12:31, 20 set 2023

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

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]