InsertionSort < Programmazione1/AA0506/PZ

---++ 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

Attachments

Topic attachments
I	Attachment	History	Action	Size	Date	Who	Comment
c	insertionSort.c	r2 r1	manage	1.7 K	2002-11-15 - 18:53	MarcoEsposito	Un semplice programma di prova

This topic: Programmazione1/AA0506/PZ > WebHome > AppuntiEsercitazioni2002 > InsertionSort
Topic revision: r5 - 2003-10-04 - AndreaSterbini