Insertion sort: differenze tra le versioni

Versione delle 09:30, 31 gen 2023

Versione attuale delle 09:32, 25 feb 2025

(17 versioni intermedie di 9 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]]

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

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

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

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

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

}}

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)

'''for''' i ← 1 '''to''' length[A]-1 '''do'''

value ← A[i]

j ← i-1

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]

Riga 89:

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

Anche il caso medio ha complessità quadratica, il che lo rende impraticabile per ordinare sequenze grandi.

Pur avendo complessità elevata, tuttavia, risulta essere l'algoritmo di ordinamento più veloce per array piccoli. Un algoritmo simile all'Insertion Sort ma dalla complessità minore è lo [[Shell sort]]. Anche lo shell sort non è in grado di competere con la combinazione dell'insertion sort con un algoritmo di tipo ''[[divide et impera (informatica)|divide et impera]]'', quale il [[quick sort]] o il [[merge sort]], ossia all'uso dell'algoritmo ''divide et impera'' per ridurre il problema all'ordinamento di sequenze di dimensione inferiore a una certa soglia, che verranno trattate con l'insertion sort(mamt).

== Bibliografia ==

Riga 95:

== Altri progetti ==

{{interprogetto|b=Implementazioni di algoritmi/Insertion sort|b_oggetto=implementazioni|b_preposizione=didell'|preposizione=sull'}}

== Collegamenti esterni ==

* {{FOLDOC}}

{{ordinamento}}