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