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.

/* 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

Topic attachments
I Attachment History Action Size Date Who Comment
C source code filec insertionSort.c r2 r1 manage 1.7 K 2002-11-15 - 18:53 MarcoEsposito Un semplice programma di prova
Edit | Attach | Watch | Print version | History: r5 < r4 < r3 < r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r5 - 2003-10-04 - AndreaSterbini






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback