Insertion Sort

/* insertionSort */
void insertionSort(int *v, int dim)
{
   int x,i,j;

   /* parte dal penultimo elemento del vettore da ordinare */ 
   for(i = dim - 2; i >= 0; i--)
   {
      /* fa una copia dell'elemento corrente "i" cioè v[i] */
      x = v[i];

      /* v[j] e l'elemento successivo di v[i] */
      j = i---+ 1;

      /* fa un ciclo che si ripete finchè j è minore della 
       * dimensione del vettore e finch� non trovo un elemento
       * successivo(v[j]) più grande di x (cioè la copia di v[i]).
       * In sostanza questo ciclo sposta di una posizione a sinistra
       * tutti gli elementi minori di x, e quando ne trova uno 
       * maggiore "inserisce" l'elemento x prima di esso.*/
      while((j < dim) && (v[j] < x))
      {
         v[j - 1] = v[j]; /* sposta a sinistra un elemento */
         j---++; /* passa al prossimo elemento */
      }

      /* inserisce dopo lo spostamento l'elemento "x". 
       * Anche se non c'è stato nessuno spostamento copia l'elemento 
       * su se stesso */
      v[j-1] = x; 
   }
}

-- MarcoEsposito - 15 Nov 2002

• insertionSort.c: Un semplice programma di prova