Introduzione

Selection sort

void selectionSort(int vettore[], int n)

{
   int i, j, posMin, tmp;

   for(i = 0; i < n - 1; ++i)
   {
      posMin = i;
      for(j = i + 1; j < n; ++j) if(vettore[j] < vettore[posMin]) posMin = j;
      tmp = vettore[i];
      vettore[i] = vettore[posMin];
      vettore[posMin] = tmp;
   }

   return;
}

Insertion sort

void insertionSort(int vettore[], int n)
{
   int i, j, val;

   for(i = 1; i < n; ++i)
   {
      val = vettore[i];
      j = i - 1;
      while(j >= 0 && vettore[j] > val)
      {
         vettore[j + 1] = vettore[j];
         j--;
      }
      vettore[j + 1] = val;
   }

   return;
}

Exchange sort o "Bubble sort"

void exchangeSort(int vettore[], int n)
{
   int i, j, val;

   for(i = 0; i < n - 1; ++i)
   {
      for(j = 0; j < n - 1 - i; ++j)
      {
         if(vettore[j] > vettore[j + 1])
         {
            val = vettore[j];
            vettore[j] = vettore[j + 1];
            vettore[j + 1] = val;
         }
      }
   }

   return;
}

void exchangeSort(int vettore[], int n)
{
   int i, j, val, goOn;

   goOn = 1;
   for(i = 0; i < n - 1 && goOn == 1; ++i)
   {
      goOn = 0;
      for(j = 0; j < n - 1 - i; ++j)
      {
         if(vettore[j] > vettore[j + 1])
         {
            val = vettore[j];
            vettore[j] = vettore[j + 1];
            vettore[j + 1] = val;
            goOn = 1;
         }
      }
   }

   return;
}

Prestazioni degli algoritmi di ordinamento

Conteggio del tempo di ordinamento di vettori casuali

Misura del tempo

#include <time.h>
.
.
.
   float t0, t1, tempo;
.
.
.
   t0 = ((float) clock()) / CLOCKS_PER_SEC;
   .
   .
   .
   /* Porzione di programma di cui si vuole calcolare il tempo. */
   .
   .
   . 
   t1 = ((float) clock()) / CLOCKS_PER_SEC;
   tempo = t1 - t0;
.
.
.

Generazione di numeri casuali

Programma per la rilevazione dei tempi di ordinamento dei vari algoritmi

/* Si scriva un programma in linguaggio C in gado di:
   * definire una costante intera N arbitrariamente grande (#define N ...)
   * generare casualmente un vettore di N valori reali
   * ordinare (per ordine numerico crescente) tale vettore con gli
     algoritmi di selezione (selection sort), inserzione (insertion sort)
     e scambio (exchange sort o bubble sort)
   * valutare le prestazioni di tali algorimi misurandone il tempo di
     esecuzione al crescere di N.

   Osservazioni:
   * Si consiglia di generare (casualmente) il vettore e di farne una
     copia in un vettore ausiliario prima di effettuarne l'ordinamento.
     In questo modo e' possibile valutare gli algoritmi di ordinamento  
     esattamente sulla stessa istanza del vettore.
   * Si consiglia inoltre di sviluppare il programma utilizzando alcune
     funzioni quali ad esempio:
     * void createArray (float vet[N]);
     * void copyArray (float vet1[N], vet2[N])
     * void selectionSort (float vet[N]);
     * void insertionSort (float vet[N]);
     * void exchangeSort (float vet[N]);

   Programma creato da: Antonio Francesco Sardella
   Ultima modifica: sabato 8 marzo 2008 11.29
   GNU GCC compiler on OpenSUSE 10.3
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 100000

/* Prototipi delle funzioni. */
void createArray(float []);
void copyArray(float [], float []);
void selectionSort(float []);
void insertionSort(float []);
void exchangeSort(float []);

/* FUNZIONE PRINCIPALE */
int main()
{
   float originario[N], copia[N], t0, t1;
   char ripeti;
   
   printf("Valutazione di tempo degli algoritmi di ordinamento.\n\n");
   printf("Programma creato da: Antonio Francesco Sardella\n");
   printf("Ultima modifica: sabato 8 marzo 2008 11.29\n");
   printf("GNU GCC compiler on OpenSUSE 10.3\n\n");
   do
   {
      /* Generazione vettore di numeri casuali. */
      createArray(originario);

      /* Creazione copia del vettore e controllo del tempo per ordinamento "selection sort". */
      copyArray(originario, copia);
      t0 = ((float) clock()) / CLOCKS_PER_SEC;
      selectionSort(copia);
      t1 = ((float) clock()) / CLOCKS_PER_SEC;
      printf("L'ordinamento Selection Sort ha impiegato %0.3f secondi...\n", t1 - t0);

      /* Creazione copia del vettore e controllo del tempo per ordinamento "insertion sort". */
      copyArray(originario, copia);
      t0 = ((float) clock()) / CLOCKS_PER_SEC;
      insertionSort(copia);
      t1 = ((float) clock()) / CLOCKS_PER_SEC;
      printf("L'ordinamento Insertion Sort ha impiegato %0.3f secondi...\n", t1 - t0);

      /* Creazione copia del vettore e controllo del tempo per ordinamento "exchange sort". */
      copyArray(originario, copia);
      t0 = ((float) clock()) / CLOCKS_PER_SEC;
      exchangeSort(copia);
      t1 = ((float) clock()) / CLOCKS_PER_SEC;
      printf("L'ordinamento Exchange Sort (Bubble Sort) ha impiegato %0.3f secondi...\n", t1 - t0);

      do
      {   
         printf("Vuoi ripetere il programma? Rispondi (s)i oppure (n)o.\n");
         scanf("%1s", &ripeti);
         printf("\n");
         if((ripeti != 's') && (ripeti != 'n')) printf("ERRORE!!! Risposta sconosciuta!!! Per favore prova ancora.\a\n\n");
      }
      while((ripeti != 's') && (ripeti != 'n'));
   }
   while(ripeti == 's');
   
   return 0;   
}



/* Funzione che crea un vettore di numeri casuali. */
void createArray(float vettore[])
{
   int cont, seme;
   
   seme = 1;
   srand((unsigned int) seme);
   for(cont = 0; cont < N; ++cont) vettore[cont] = ((float) rand()) / ((float) RAND_MAX);

   return;
}

/* Funzione che crea una copia del vettore. */
void copyArray(float vettore[], float duplicato[])
{
   int cont;

   for(cont = 0; cont < N; ++cont) duplicato[cont] = vettore[cont];   

   return;
}

/* Ordinamento Selection Sort. */
void selectionSort(float vettore[])
{
   int i, j, posMin;
   float tmp;

   for(i = 0; i < N - 1; ++i)
   {
      posMin = i;
      for(j = i + 1; j < N; ++j) if(vettore[j] < vettore[posMin]) posMin = j;
      tmp = vettore[i];
      vettore[i] = vettore[posMin];
      vettore[posMin] = tmp;
   }

   return;
}

/* Ordinamento Insertion Sort. */
void insertionSort(float vettore[])
{
   int i, j;
   float val;

   for(i = 1; i < N; ++i)
   {
      val = vettore[i];
      j = i - 1;
      while(j >= 0 && vettore[j] > val)
      {
         vettore[j + 1] = vettore[j];
         j--;
      }
      vettore[j + 1] = val;
   }

   return;
}

/* Ordinamento Exchange Sort. */
void exchangeSort(float vettore[])
{
   int i, j;
   float val;

   for(i = 0; i < N - 1; ++i)
   {
      for(j = 0; j < N - 1 - i; ++j)
      {
         if(vettore[j] > vettore[j + 1])
         {
            val = vettore[j];
            vettore[j] = vettore[j + 1];
            vettore[j + 1] = val;
         }
      }
   }

   return;
}

Conclusioni