Implementazioni di algoritmi/Insertion sort
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
modificaSegue lo pseudocodice per l'algoritmo.
insertion_sort(x[], n) for i ← 1 to n - 1 do app ← x[i] j ← i - 1 while (j >= 0) and (x[j] > app) do x[j + 1] ← x[j] j ← j - 1 x[j + 1] ← app
Segue lo pseudocodice per linguaggi funzionali.
insert :: Ord a => a -> [a] -> [a] insert item [] = [item] insert item (h:t) | item <= h = item:h:t | otherwise = h:(insert item t) insertsort :: Ord a => [a] -> [a] insertsort [] = [] insertsort (h:t) = insert h (insertsort t)
Implementazioni
modificaSeguono alcuni esempi di implementazione in vari linguaggi di programmazione.
void insertion_sort(int array[], int N)
{
int i, j,
value;
for (i = 1; (i < N); i++)
{
for (value = array[i], j = i - 1;
((j >= 0) && (array[j] > value));
j--)
array[j + 1] = array[j];
if (j + 1 != i)
array[j + 1] = value;
}
}
static void Main(string[] Args)
{
int[] A ={};
int key,i,k,t;
int n = A.Length;
//Dichiarazione e inizializzazione di variabili
//n è il numero di elementi contenuti nell'array
for (k = 1; k < n; ++k)
{
key = A[k];
i = k-1;
while ((i >= 0) && (key < A[i]))
{
A[i+1] = A[i];
i--;
}
A[i+1] = key;
}
//Un piccolo accorgimento per vedere se tutto funziona correttamente
for (t = 0; t < n; t++)
{
Console.WriteLine("L'ordine è: {0}", A[t]);
}
Console.ReadLine();
}
public static void insertionSort(int[] array) {
int j; //N.B. dichiaro qui j altrimenti non può essere vista dall'ultima istruzione
for (int i = 1; i < array.length; i++) {
int tmp = array[i]; // l'elemento viene rimosso dalla lista
for (j = i - 1; (j >= 0) && (array[j] > tmp); j--) {
array[j + 1] = array[j];
}
array[j + 1] = tmp; // l'elemento rimosso viene reinserito nella giusta posizione
// del sottoinsieme ordinato 0..i
}
}
def insertionsort(array):
for removed_index in range(1, len(array)):
removed_value = array[removed_index]
insert_index = removed_index
while insert_index > 0 and array[insert_index - 1] > removed_value:
array[insert_index] = array[insert_index - 1]
insert_index = insert_index - 1
array[insert_index] = removed_value
SUBROUTINE SSORT (X, IY, N, KFLAG)
IMPLICIT NONE
DO 100 I=2,N
IF ( X(I).GT.X(I-1) ) THEN
DO 50 J=I-2,1,-1
IF(X(I).LT.X(J)) go to 70
50 CONTINUE
J=0
70 TEMP=X(I)
ITEMP=IY(I)
DO 90 K=I,J+2,-1
IY(K)=IY(K-1)
90 X(K)=X(K-1)
X(J+1)=TEMP
IY(J+1)=ITEMP
ENDIF
100 CONTINUE
RETURN
END
(define insert
(lambda (n l)
(cond ((null? l) (list n))
(else
(if (< n (car l)) (cons n l)
(cons (car l) (insert n (cdr l)))))))
Altri progetti
modifica- Wikipedia contiene una voce su questo algoritmo
- Wikimedia Commons contiene immagini o altri file su insertion sort