Implementazioni di algoritmi/Insertion sort

Wikibooks, manuali e libri di testo liberi.

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.

[modifica] 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)

[modifica] Implementazioni

Seguono alcuni esempi di implementazione in vari linguaggi di programmazione.

[modifica] C

void InsertionSort(int a[], int n) 
{
   int i, j, temp;
 
   for (j = 1; j < n; j++)
   {
      temp = a[j];
      i=j-1;       
      while(i>=0 && temp< a[i])
      {
         a[i+1] = a[i];
         i=i-1;
      }
 
      a[i + 1] = temp;
   }
}

La funzione qui riportata riceve due parametri: a è l'array da ordinare, n è il numero dei suoi elementi detto Size.

[modifica] 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
     }
}

[modifica] 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

[modifica] 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

[modifica] 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)))))))

[modifica] Altri progetti

• Wikipedia contiene una voce riguardante questo algoritmo