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

Segue 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

Seguono alcuni esempi di implementazione in vari linguaggi di programmazione.

C

typedef int item_t;
 
void insertion_sort(item_t* const array, size_t size)
{
   int i, j;
   item_t value;
 
   for(i = 1; i < size; i++)
   {
      value = array[i];
      j = i - 1;
 
      for(; (j >= 0) && (value < array[j]); j--)
         array[j + 1] = array[j];
 
      array[j + 1] = value;
   }
}

C#

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 contentuti 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();
        }

Java

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

Python

 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

FORTRAN

      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

Lisp

 (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

• Wikipedia

• Wikipedia contiene una voce riguardante questo algoritmo