Algoritmi in pillole C: ordinamento con insertion sort

Animazione dell'algoritmo Insertion sort da Wikipedia

Se l'ordine desiderato è quello crescente,  l'algoritmo parte dall'ipotesi che l'array da ordinare sia composto da un primo elemento ordinato e una seconda parte "disordinata". Esamina quindi il primo elemento disordinato confrontandolo con tutti gli elementi "ordinati". Ad ogni confronto, se l'elemento disordinato è minore di quello ordinato si "inserisce", da qui il nome dell'algoritmo, l'elemento disordinato al posto di quello ordinato, scambiandoli di posto. Al termine di questa fase si avrà una parte ordinata composta da due elementi e una parte disordinata composta da N-2 elementi. L'algoritmo continua ad esaminare la parte disordinata fino alla fine dell'array.

Pseudocodice:

"per i che varia da 1 a N
   per j che varia da i a 0
     se l'elemento j è minore dell'elemento i allora
       scambia l'elemento i con l'elemento j"

Codice:

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

La complessità computazionale asintotica è O(n^2).

Caso peggiore: array ordinato in senso inverso - T. esec. prop. a n^2
Caso migliore: array già ordinato                      - T. esec. prop. a n