001: // Quicksort
002: #include<stdio.h>
003: #include<stdlib.h>
004: #include<time.h>
005: 
006: void stampaarray(int *, int);
007: 
008: void quicksort(int *x, int primo, int ultimo)  // prototipo differente rispetto a bubble sort, indico anche quale parte dell'array va ordinata
009: {
010:   if (primo >= ultimo) return;                 // condizione uscita della ricorsione, se array ha dimensione nulla o solo un elemento esco
011: 
012:   int pivot = x[primo];                        //prendiamo, per semplicita', come pivot il primo elemento della sequenza 
013: 
014:   int i = primo+1;                             // i e j li imposto come indice del primo e ultimo elemento della parte
015:   int j = ultimo;                              // di array da ordinare
016:   while (i < j)  
017:   { 
018:     while (i < ultimo && x[i] <= pivot)        // cerca, partendo da sinistra, il primo elemento > pivot
019:       i++;
020:     while (j > primo && x[j] > pivot)          // cerca, partendo da destra, il primo elemento < pivot
021:       j--;
022:     if (i < j)                                 // li scambia
023:     {
024:       int temp = x[i];
025:       x[i] = x[j];
026:       x[j] = temp;
027:     }
028:   }
029: 
030:   int temp = x[primo];                         // ho "diviso" l'array in due sottoarray: da un lato elementi <= pivot, dall'altro > pivot
031:   x[primo] = x[j];                             // metto il pivot in mezzo tra questi due sottoarray
032:   x[j] = temp;
033: 
034:   
035:   quicksort(x,primo, j-1);                    // ordino ricorsivamente i due sottoarray
036:   quicksort(x,j+1, ultimo);                   // il pivot lo escludo in quanto gia' in posizione corretta
037: }
038: 
039: 
040: int main(int argc, char **argv)
041: {
042:    int i, j, n, *a;
043:    clock_t start,stop; // misureremo i tempi
044:    double quick; // stima velocità
045: 
046: 
047:    if(argc<2){
048:      fprintf(stderr,"errore, manca l'argomento numerico\n");
049:      exit(EXIT_FAILURE);
050:    }
051:    n=atoi(argv[1]);
052:    a=malloc(sizeof(*a)*n);
053: 
054:    srand(time(0));
055: 
056:    // genera array
057:    for (i=0; i<n; i++)
058:      a[i]=(i+1);
059: 
060:    // mescola gli elementi dell'array
061:    for (i=0; i<n; i++){
062:      j = rand()%n;
063:      int t = a[i];
064:      a[i] = a[j];
065:      a[j] = t;
066:    }
067: 
068:    // visualizza array mescolato
069:    printf(" Array da ordinare\n");
070:    stampaarray(a,n);
071: 
072:    getchar();
073: 
074:    // inizio cronometro
075:    start=clock(); // restituisce il "CPU time" 
076: 
077:    // invoco ordinamento
078:    quicksort(a,0,n-1);
079: 
080:    //fine cronometro
081:    stop=clock();
082:    quick=(double)stop-start; // se voglio i secondi divido per CLOCKS_PER_SEC
083: 
084:    // visualizza array ordinato
085:    printf(" Array ordinato\n");
086:    stampaarray(a,n);
087: 
088:    printf("\n");
089: 
090:    printf("\nTempo di esecuzione quicksort: %g\n",quick/CLOCKS_PER_SEC);
091: 
092: 
093:    return 0;
094: }
095: 
096: 
097: void stampaarray(int *a, int n){
098:   int i;
099:   if(n < 200)
100:   {
101:     for (i = 0; i < n; i++){
102:       printf("%5d ",a[i]);
103:       printf((i+1)%15 ? "" : "\n");
104:     }
105:   }
106:   else
107:   {
108:     printf(" Array troppo grosso, mi limito a stampare i primi 30 e gli ultimi 30 elementi\n");
109: 
110:     for (i = 0; i < 30; i++){
111:       printf("%5d ",a[i]);
112:       printf((i+1)%15?"":"\n");
113:     }
114:      printf("  ...\n");
115:     for (i = n - 30; i < n; i++){
116:       printf("%5d ",a[i]);
117:       printf((n-i-1)%15?"":"\n");
118:     }
119:   }
120: 
121:    printf("\n");
122: }
123: 
124: 
125: 
126: