Ordinamento: Insertion Sort

Problema: Data una sequanza di $n$ numeri $A= [a_0,\, \dots\,, a_{n-1}]$, ordinarla in modo crescente.
Soluzione: Iterativa (Insertion sort)
Complessità: $O(n^2)$ nel caso peggiore

Insertion sort si basa sul classico metodo divide et impera. Se abbiamo una sequenza di $n$ numeri, dunque, per prima cosa si cercherà di ordinare la sottosequenza formata dai primi due elementi (quella formata dal solo primo elemento è già ordinata per definizione) e si sfrutterà tale sottosequenza appena ordinata (formata dai primi due elementi) per ordinare la sottosequenza formata dai primi 3 elementi, e così via.

Volendo fare un esempio concreto, definiamo la sequenza $A= [6, 3, 5, 7, 2, 4]$ ed indichiamo con il grigio la sottosequenza di elementi già ordinati e con il verde l'elemento aggiuntivo da ordinare rispetto alla sottosequenza grigia appena ordinata. Si parte con il primo elemento grigio già ordinato per definizione e con il secondo elemento in verde che si vuole ordinare rispetto al primo.
Il valore del primo elemento è maggiore del secondo, quindi vengono scambiati e la prima iterazione del ciclo è conclusa. Se il primo elemento fosse stato minore o uguale l'iterazione si sarebbe conclusa senza scambio.

Alla seconda iterazione la situazione è questa

I primi due elementi sono stati ordinati nella prima iterazione. Ora si aggiunge il terzo e si vuole ordinarlo rispetto alla sottosequenza grigia già ordinata. A questo scopo è sufficiente scorrere all'indietro la sottosequenza grigia (con un ciclo innestato all'interno di quello visto in precedenza che scorre la sequenza in avanti per aggiungere elementi in verde) fino a quando si trovano valori maggiori di 5. A quel punto tutti gli elementi maggiori di 5 vengono scalati di un posto in avanti e l'iterazione del ciclo interno si conclude. Nel ciclo esterno il 5 prende la posizione dell'ultimo valore scalato e si conclude anche l'iterazione del ciclo esterno. Tale procedura si ripete fino a quando non si processa l'ultimo elemento della sequenza.

#include <stdio.h>
 
void insertion_sort(int*, int);
void print_vector(int*, int);
 
int main(int argc, char *argv[], char *envp[])
{
 int a[6] = { 6, 3, 5, 7, 2, 4 };
 int n = sizeof(a) / sizeof(int);
 insertion_sort(a, n);
 print_vector(a, n);
 
 return 0;
}
 
void insertion_sort(int *a, int n)
{
 for (int i = 1; i < n; ++i)
 {
  int curr = a[i];
  int j = i - 1;
  for (; j >= 0 && a[j] > curr; --j)
  {
   a[j + 1] = a[j];
  }
  a[j + 1] = curr;
 }
}
 
void print_vector(int *m, int n)
{
 for (int i = 0; i < n; ++i)
 {
  printf("%d ", m[i]);
 }
 printf("\n");
}

Riferimenti
[1] Introduzione agli algoritmi e strutture dati - Cormen, Leiserson, Rivest, Stein
[2] https://it.wikipedia.org/wiki/Insertion_sort