Insertion sort: differenze tra le versioni

Versione delle 13:23, 19 feb 2017

Versione attuale delle 09:32, 25 feb 2025

(45 versioni intermedie di 31 utenti non mostrate)

Riga 1:

{{Algoritmo

|classclasse = [[Algoritmo di ordinamento]]

|imageimmagine =Insertion Sorting insertion sort animationanim.gif

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

|datastruttura dati = [[Array]]

|timetempo = <math>O(''n''<sup>^2)</supmath>)

|tempo migliore = <math>O(n)</math>

|best-time=O(''n'')

|average-timetempo medio = <math>O(''n''<sup>^2)</supmath>)

|spacespazio = <math>O(''n'')</math> totale<br /><math>O(''1'')</math> ausiliaria

|optimalottimale = Sì (nel caso di inserimento di alcuni valori in una lista quasi ordinata) altrimenti No

}}

[[File:Insertion-sort-example-300px.gif|300pxupright=1.4|thumb|right|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.

Riga 25 ⟶ 24:

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

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

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

Riga 32 ⟶ 31:

j ← i-1

'''while''' j >= 0 '''and''' A[j] > value '''do'''

A[j + 1] ← A[j]

j ← j-1

A[j+1] ← value;

=== Algoritmo [[Algoritmo ricorsivo|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{{' }}''n-1''-esimo elemento.

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

Riga 45 ⟶ 44:

value ← A[n-1]

j ← n-2

'''while''' j >= 0 '''and''' A[j] > value '''do'''

'''do''' A[j + 1] ← A[j]

j ← j-1

A[j+1] ← value

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

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

Riga 58 ⟶ 57:

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

insertsort [] = []

insertsort (h:t) = insert h (insertsort t)

Riga 64 ⟶ 63:

=== Esempio di funzionamento ===

[[File:AnimazioneInsertionSort.gif|left|thumb|upright=2.2|Simulazione dell'insertion sort su di un array]]

Di seguito sono mostrati i passi compiuti dall'algoritmo per ordinare la sequenza [3, 7, 4, 9, 5, 2, 6, 1]. In ogni passo, l'elemento sottolineato è quello considerato, mentre quello in grassetto è l'elemento spostato nel passo precedente.

Riga 86 ⟶ 85:

'''1''' 2 3 4 5 6 7 9

== Analisi delle prestazioni ==

Il caso ottimo per l'algoritmo è quello in cui la sequenza di partenza sia già ordinata. In questo caso, l'algoritmo ha tempo di esecuzione lineare, ossia <math>\Theta(n)</math>. Infatti, in questo caso, in ogni iterazione il primo elemento della sottosequenza non ordinata viene confrontato solo con l'ultimo della sottosequenza ordinata.

Il caso pessimo è invece quello in cui la sequenza di partenza sia ordinata al contrario. In questo caso, ogni iterazione dovrà scorrere e spostare ogni elemento della sottosequenza ordinata prima di poter inserire il primo elemento della sottosequenza non ordinata. Pertanto, in questo caso l'algoritmo di insertion sort ha complessità temporale quadratica, ossia <math>\Theta(n^2)</math>.

Riga 96 ⟶ 95:

== Altri progetti ==

{{Interprogetto|commons=Category:Insertion sortinterprogetto|b=Implementazioni di algoritmi/Insertion sort|b_oggetto=implementazioni|b_preposizione=didell'|preposizione=sull'}}

== Collegamenti esterni ==

* {{FOLDOC}}

{{ordinamento}}

{{portale|informatica}}

[[Categoria:Algoritmi di ordinamento]]