L’Insertion Sort è tra i primi algoritmi di ordinamento, che vengono affrontati nel linguaggio C.
E’ un algoritmo di ordinamento basato sui confronti, la sua complessità computazionale è quadratica: O(n^2).

L’implementazione così come il funzionamento è basilare, consiglio anche la visione di questo simpatico video-danza che ne mostra il funzionamento, InsertionSort AlgoRythmics :)


- Qui di seguito ecco l’algoritmo scritto in C:

void insertion_sort(int a[], int n){
int i, j, temp;
int p = 0; //indice del minimo. (consideriamo inizialmente il primo elemento come fosse il minimo)
 
    for (i = 1; i < n; i++)
     if (a[p] > a[i]) 
        p = i;
 
    temp = a[0];
    a[0] = a[p];
    a[p] = temp;
 
    //abbiamo messo il minimo nella prima posizione a[0].
    //In questo modo lo useremo come sentinella (per non sforare l'array a sinistra).
 
for(i = 2; i < n; i++){ //partiamo dal 2 indice poichè non c'è bisogno di confrontare inizialmente già con a[0] che sappiamo essere il minimo.
    j = i;
      while(a[j] < a[j-1]){
                 temp = a[j];
                 a[j] = a[j-1];
                 a[j-1] = temp;
                 j--;
                 }    
    }
 
}