InsertionSort < Programmazione1/AA0506/PZ

Tags: view all tags

---++ Insertion Sort
L'insertion sort è un ordinamento non molto veloce,ma riesce a ordinare vettori che hanno anche elementi ripetuti, vedi spiegazione "passo passo" sotto.

<PRE style="background: lightgrey;">
<verbatim>
/* 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&#65533; 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; 
   }
}
</verbatim>
</pre>




-- Users.MarcoEsposito - 15 Nov 2002
   

   * [[%ATTACHURL%/insertionSort.c][insertionSort.c]]: Un semplice programma di prova