001: // bubblesort
002: #include<stdio.h>
003: #include<stdlib.h>
004: #include<time.h>
005: 
006: void stampaarray(int *, int); 
007: 
008: // bubblesort implementation
009: void bsort(int *a, int n)
010: {                                        // takes as input: array of int and number of elements
011:   int tmp;                               // used for swaps 
012:   int sup = n-1;                         // index of last element swapped during the last pass, initially latest element
013:   int last;                              // used to track the latest swap at each round
014: 
015:   while (sup >= 0) {                     // round cycle, terminate if no more swaps needed
016:     last = -1;
017:     for (int i = 0; i < sup; i++)        // consider each element
018:       if ((a[i]>a[i+1])) {               // compare against the following one 
019:   tmp=a[i];                        // swap if not ordered
020:   a[i]=a[i+1];
021:   a[i+1]=tmp;
022:   last = i;                        // track the latest element that was swapped
023:       }
024:     sup = last;                          // elements with index > sup are alredy in the right order
025:   }
026: }
027: 
028: int main(int argc, char **argv)
029: {
030:   int i, j, n, *a;
031:   clock_t start,stop; // misureremo i tempi
032:   double quick; // stima velocità
033: 
034: 
035:   if(argc<2){
036:     fprintf(stderr,"errore, manca l'argomento numerico\n");
037:     exit(EXIT_FAILURE);
038:   }
039:   n=atoi(argv[1]);
040:   a=malloc(sizeof(*a)*n);
041: 
042:   srand(time(0));
043: 
044: 
045: 
046:   srand(time(0));
047: 
048:   // genera array
049:   for (i=0; i<n; i++)
050:     a[i]=i+1;
051:   // mescola gli elementi dell'array
052:   for (i=0; i<n; i++){
053:     j = rand()%n;
054:     int t = a[i];
055:     a[i] = a[j];
056:     a[j] = t;
057:   }
058:   // visualizza array mescolato
059:   printf(" Array da ordinare\n");
060:   stampaarray(a,n);
061: 
062:   getchar();
063: 
064:   // inizio cronometro
065:   start=clock(); // restituisce il "CPU time" 
066: 
067:   // invoco ordinamento
068:   bsort(a,n);
069: 
070:   //fine cronometro
071:   stop=clock();
072:   quick=(double)stop-start; // se voglio i secondi divido per CLOCKS_PER_SEC
073: 
074:   // visualizza array ordinato
075:   printf(" Array ordinato\n");
076:   stampaarray(a,n);
077: 
078: 
079: 
080: 
081:   printf("\n");
082: 
083:   printf("\nTempo di esecuzione bsort sort: %g\n",quick/CLOCKS_PER_SEC);
084: 
085: 
086:   return 0;
087: }
088: 
089: 
090: void stampaarray(int *a, int n){
091:   int i;
092:   if(n<200)
093:   {
094:     for (i=0; i<n; i++){
095:       printf("%5d ",a[i]);
096:       printf((i+1)%15 ? "" : "\n");
097:     }
098:   }
099:   else
100:   {
101:     printf(" Array troppo grosso, mi limito a stampare i primi 30 e gli ultimi 30 elementi\n");
102: 
103:     for (i=0; i<30; i++){
104:       printf("%5d ",a[i]);
105:       printf((i+1)%15?"":"\n");
106:     }
107:      printf("  ...\n");
108:     for (i=n-30; i<n; i++){
109:       printf("%5d ",a[i]);
110:       printf((n-i-1)%15?"":"\n");
111:     }
112:   }
113: 
114:    printf("\n");
115: }
116: 
117: