001: // Bottom up Mergesort
002: #include<stdio.h>
003: #include<stdlib.h>
004: #include<time.h>
005: 
006: void stampaarray(int *, int);
007: void merge(int *, int *, int, int, int);  // funzione di appoggio per merge dei subset
008: 
009: // prende in ingresso vettore da ordinare e relativa numerosita'
010: void mergesort(int *a, int n)
011: {
012:   int i, m;
013: 
014:   // alloca il vettore ausiliario 
015:   int *extra = malloc(sizeof(*a) * n);
016: 
017:   // m: dimensione blocco da esaminare, inizialmente 1, poi 2, 4, 8 ecc.
018:   for (m = 1; m < n - 1; m += m)
019:     // i e' l'indice dell'elemento iniziale dei blocchi "a sinistra"
020:     // ogni volta mi sposto di 2m elementi 
021:     for (i = 0; i < n - 1; i += m + m)
022:     {
023:       int from = i;          // indice primo elemento del blocco sinistro
024:       int mid  = i + m - 1;  // indice ultimo elemento del blocco sinistro
025:       // l'indice dell'ultimo elemento blocco destro sarebbe i+2m-1 
026:       // ma se la dimensione dell'array iniziale non e' potenza di due
027:       // "a destra" rischio di uscire e quindi controllo che questro indice non sia > n - 1
028:       // nel caso lo tronco a  n - 1.
029:       int to   = ((i+m+m-1) > (n - 1)) ? n - 1 : (i+m+m-1);
030: 
031:       // uso merge() per "unire in maniera ordinata" i blocchi
032:       // di a[] da indice from a indice to
033:       // usando extra come appoggio
034:       merge(a, extra, from, mid, to);
035:     }
036:   free(extra);
037: }
038: 
039: 
040: 
041: 
042: 
043: void merge(int *a, int *extra, int start, int m, int end)
044: {
045:   int i, j, k;
046: 
047:   // se il blocco "a sinistra" supera end non c'e' un blocco destro: nulla da fondere
048:   if(m>end) return;
049: 
050:   // copia SOLO la meta' sinistra a[start..m] in extra[start..m]
051:   // e' una ottimizzazione, perche'?
052:   for (i = start; i <= m; i++)
053:     extra[i] = a[i];
054: 
055:   /* Fusione:
056:    *   i - cursore su extra[start..m]   (meta' sinistra, gia' copiata)
057:    *   j - cursore su a[m+1..end]      (meta' destra, ancora in a[])
058:    *   k - cursore sulla posizione di scrittura in a[]
059:    *
060:    * Il ciclo termina appena uno dei due cursori raggiunge la fine del proprio
061:    * blocco; l'altro while sistemera' eventuali elementi rimasti 
062:    */
063:   i = start;
064:   j = m + 1;
065:   k = start;
066: 
067:   while (i <= m && j <= end) {
068:     if (extra[i] <= a[j])
069:       a[k++] = extra[i++]; // preleva dalla meta' sinistra (extra)
070:     else
071:       a[k++] = a[j++];     // preleva dalla meta' destra (a[])
072:   }
073: 
074:   /* Se restano elementi nella meta' sinistra, copiali in a[].
075:    * (Se invece restano elementi nella meta' destra, sono gia' in a[] nella
076:    * posizione giusta: non occorre fare nulla.) */
077:   while (i <= m)
078:     a[k++] = extra[i++];
079: }
080: 
081: 
082: int main(int argc, char **argv)
083: {
084:    int i, j, n, *a;
085:    clock_t start,stop; // misureremo i tempi
086:    double quick; // stima velocita'
087: 
088: 
089:    if(argc<2){
090:      fprintf(stderr,"errore, manca l'argomento numerico\n");
091:      exit(EXIT_FAILURE);
092:    }
093:    n=atoi(argv[1]);
094:    a=malloc(sizeof(*a)*n);
095: 
096:    srand(time(0));
097: 
098:    // genera array
099:    for (i=0; i<n; i++)
100:      a[i]=(i+1);
101: 
102:    // mescola gli elementi dell'array
103:    for (i=0; i<n; i++){
104:      j = rand()%n;
105:      int t = a[i];
106:      a[i] = a[j];
107:      a[j] = t;
108:    }
109: 
110:    // visualizza array mescolato
111:    printf(" Array da ordinare\n");
112:    stampaarray(a,n);
113: 
114:    getchar();
115: 
116:    // inizio cronometro
117:    start=clock(); // restituisce il "CPU time" 
118: 
119:    // invoco ordinamento
120:    mergesort(a,n);
121: 
122:    //fine cronometro
123:    stop=clock();
124:    quick=(double)stop-start; // se voglio i secondi divido per CLOCKS_PER_SEC
125: 
126:    // visualizza array ordinato
127:    printf(" Array ordinato\n");
128:    stampaarray(a,n);
129: 
130:    printf("\n");
131: 
132:    printf("\nTempo di esecuzione quicksort: %g\n",quick/CLOCKS_PER_SEC);
133: 
134: 
135:    return 0;
136: }
137: 
138: 
139: void stampaarray(int *a, int n){
140:   int i;
141:   if(n < 200)
142:   {
143:     for (i = 0; i < n; i++){
144:       printf("%5d ",a[i]);
145:       printf((i+1)%15 ? "" : "\n");
146:     }
147:   }
148:   else
149:   {
150:     printf(" Array troppo grosso, mi limito a stampare i primi 30 e gli ultimi 30 elementi\n");
151: 
152:     for (i = 0; i < 30; i++){
153:       printf("%5d ",a[i]);
154:       printf((i+1)%15?"":"\n");
155:     }
156:      printf("  ...\n");
157:     for (i = n - 30; i < n; i++){
158:       printf("%5d ",a[i]);
159:       printf((n-i-1)%15?"":"\n");
160:     }
161:   }
162: 
163:    printf("\n");
164: }
165: 
166: 
167: 
168: