Implementazioni di algoritmi/Insertion sort: differenze tra le versioni

Contenuto cancellato Contenuto aggiunto
m ha spostato Insertion sort a Algoritmi/Insertion sort: sposto in base a convenzioni di nomenclatura
link a pedia, template indice e interprogetto
Riga 1:
{{algoritmi}}
L''''Insertion sort''', in italiano '''ordinamento a inserimento''', è un [[algoritmo]] relativamente semplice per ordinare un [[array]]. Esso è un [[Algoritmo in loco|algoritmo ''in place'']], cioè ordina l'array senza doverne creare un altro “di appoggio”, quindi risparmia memoria.
 
L''''Insertion sort''', in italiano '''ordinamento a inserimento''', è un [[w:algoritmo|algoritmo]] relativamente semplice per ordinare un [[w:array|array]]. Esso è un [[w:Algoritmo in loco|algoritmo ''in place'']], cioè ordina l'array senza doverne creare un altro “di appoggio”, quindi risparmia memoria.
 
Non è molto diverso dal modo in cui un essere umano, spesso, ordina un mazzo di carte. L'algoritmo utilizza due indici: il primo punta inizialmente al secondo elemento dell'array, il secondo inizia dal primo. Se il primo elemento è maggiore del secondo, i due valori vengono scambiati. Poi il primo indice avanza di una posizione e il secondo indice riparte dall'elemento precedente quello puntato dal primo. Se l'elemento puntato dal secondo indice non è maggiore di quello a cui punta il primo indice, il secondo indice avanza; e così fa, finché si trova nel punto in cui il valore del primo indice deve essere ''inserito'' (da qui ''insertion''). L'algoritmo così tende a spostare man mano gli elementi maggiori verso destra.
 
Pur avendo complessità quadratica, per array piccoli è solitamente l'algoritmo di ordinamento più veloce. Un algoritmo simile all'Insertion Sort ma dalla complessità minore è lo [[w:Shell sort|Shell sort]]. Tuttavia, anche lo shell sort non è in grado di competere con la combinazione dell'insertion sort con un algoritmo di tipo ''divide et impera'', quale il [[w:quick sort|quick sort]] o il [[w:merge sort|merge sort]].
 
==Pseudocodice==
Segue lo [[w:pseudocodice|pseudocodice]] per l'algoritmo.
 
insertion_sort(x[], n)
Line 29 ⟶ 31:
 
==Implementazioni==
{{Trasferimento|wb|Implementazioni}}
 
Seguono alcuni esempi di implementazione in vari [[w:linguaggi di programmazione|linguaggi di programmazione]].
 
===[[w:linguaggio C|C]]===
 
<source lang=C>
Line 56 ⟶ 57:
La funzione qui riportata riceve due parametri: ''x'' è l'array da ordinare, ''n'' è il numero dei suoi elementi.
 
===[[w:linguaggio Java|Java]]===
 
<source lang=java>
Line 77 ⟶ 78:
</source>
 
===[[w:Python|Python]]===
 
<source lang=python>
Line 90 ⟶ 91:
</source>
 
===[[w:FORTRAN|FORTRAN]]===
 
<source lang=FORTRAN>
Line 115 ⟶ 116:
</source>
 
===[[w:Lisp|Lisp]]===
 
<source lang=Lisp>
Line 126 ⟶ 127:
</source>
 
== Altri progetti ==
{{interprogetto|w=Insertion sort|w_etichetta=questo algoritmo}}
 
[[Categoria:Algoritmi| di ordinamento]]
{{Avanzamento|100%|4 marzo 2008}}
 
[[ar:ترتيب بالإدراج]]
[[da:Indsættelsessortering]]
[[de:Insertionsort]]
[[en:Insertion sort]]
[[es:Ordenamiento por inserción]]
[[et:Vahelepanemisega sortimine]]
[[fi:Lisäyslajittelu]]
[[fr:Tri par insertion]]
[[he:מיון הכנסה]]
[[is:Innsetningarröðun]]
[[ja:挿入ソート]]
[[ko:삽입 정렬]]
[[lt:Įterpimo rikiavimo algoritmas]]
[[nl:Insertion sort]]
[[no:Sortering ved innsetting]]
[[pl:Sortowanie przez wstawianie]]
[[pt:Insertion sort]]
[[ru:Сортировка вставками (простыми включениями)]]
[[tr:Eklemeli Sıralama]]
[[uk:Сортування включенням]]
[[vi:Sắp xếp chèn]]
[[zh:插入排序]]