# Implementazioni di algoritmi/Insertion sort

Implementazioni di algoritmi
Copertina Tutti i moduli · Sviluppo
    CopertinaImplementazioni di algoritmi/Copertina
* Algoritmo di EuclideImplementazioni di algoritmi/Algoritmo di Euclide
* Elevazione a potenzaImplementazioni di algoritmi/Elevazione a potenza
* Prodotto scalareImplementazioni di algoritmi/Prodotto scalare
* Calcolo della PasquaImplementazioni di algoritmi/Calcolo della Pasqua
* Metodo Monte CarloImplementazioni di algoritmi/Metodo Monte Carlo
* Ricerca
** Ricerca dicotomicaImplementazioni di algoritmi/Ricerca dicotomica
* Numeri primi
** Crivello di EratosteneImplementazioni di algoritmi/Crivello di Eratostene
** Test di primalità
*** Test deterministicoImplementazioni di algoritmi/Test deterministico
*** Test di Miller-RabinImplementazioni di algoritmi/Test di Miller-Rabin
* PRNG
** Mersenne TwisterImplementazioni di algoritmi/Mersenne Twister
** Test Chi QuadratoImplementazioni di algoritmi/Test Chi Quadrato
* Crittografia
** RSAImplementazioni di algoritmi/RSA
** TEAImplementazioni di algoritmi/TEA
* π(Metodi per definire il pi greco)
** Pi grecoImplementazioni di algoritmi/Pi greco
* Algoritmi di ordinamento
** Bubble sortImplementazioni di algoritmi/Bubble sort
** Bucket sortImplementazioni di algoritmi/Bucket sort
** Counting sortImplementazioni di algoritmi/Counting sort
** Gnome sortImplementazioni di algoritmi/Gnome sort
** Insertion sortImplementazioni di algoritmi/Insertion sort
** Merge sortImplementazioni di algoritmi/Merge sort
** QuicksortImplementazioni di algoritmi/Quicksort
** Radix sortImplementazioni di algoritmi/Radix sort
** Selection sortImplementazioni di algoritmi/Selection sort
** Shaker sortImplementazioni di algoritmi/Shaker sort
** Shell sortImplementazioni di algoritmi/Shell sort
Modifica il sommario
L'Insertion sort, in italiano ordinamento a inserimento, è un algoritmo relativamente semplice per ordinare un array. Esso è un 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 indietreggia; 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 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 quick sort o il merge sort.

## Pseudocodice

Segue lo pseudocodice per l'algoritmo.
Segue lo pseudocodice per linguaggi funzionali.

## Implementazioni

Seguono alcuni esempi di implementazione in vari linguaggi di programmazione.

### Lisp
## Altri progetti

Altri progetti
* Wikipedia
* Wikimedia Commons
* Wikipedia contiene una voce su questo algoritmo
* Wikimedia Commons contiene immagini o altri file su insertion sort