1 /*
 2    Copyright (C) 2014 Alessandro Bugatti (alessandro.bugatti@istruzione.it)
 3  
 4    This program is free software; you can redistribute it and/or
 5    modify it under the terms of the GNU General Public License
 6    as published by the Free Software Foundation; either version 2
 7    of the License, or (at your option) any later version.
 8  
 9    This program is distributed in the hope that it will be useful,
10    but WITHOUT ANY WARRANTY; without even the implied warranty of
11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12    GNU General Public License for more details.
13  
14    You should have received a copy of the GNU General Public License
15    along with this program; if not, write to the Free Software
16    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
17  */
18  
19  /*! \file
20   *  \brief Algoritmo di ordinamento Merge Sort che ordina
21   *  un vettore di N interi
22   *  \author Alessandro Bugatti
23   *
24   *  \version 0.1
25   *  \date  Creazione  20/09/2014
26   *  \date  Ultima modifica 20/09/2014
27   */
28  
29  #include <stdio.h>
30  #include <stdlib.h>
31  #include <time.h>
32  
33  #define N 5000000
34  
35  int v[N], aux[N];
36  
37  int merge(int a[], int l,int m, int r)
38  {
39      int i=l,j=m+1,k=0;
40      for(;;)
41      {
42          if(a[i]<a[j])
43              aux[k] = a[i++];
44          else
45              aux[k] = a[j++];
46          k++;
47          if(i>m || j>r) break;
48      }
49      for (;i<=m;i++,k++)
50          aux[k] = a[i];
51      for (;j<=r;j++,k++)
52          aux[k] = a[j];
53      for (i=l,j=0; i < l+k; i++,j++)
54          a[i]=aux[j];
55  }
56  
57  void sort(int a[],int l, int r)
58  {
59      int m;
60      if (r<=l) return;
61      m = (l+r)/2;
62      sort(a,l,m);
63      sort(a,m+1,r);
64      merge(a,l,m,r);
65  }
66  
67  
68  
69  int main(int argc, char *argv[])
70  {
71      int i;
72      clock_t start, end;
73      double cpu_time_used;
74      srand(time(NULL));
75      for (i=0; i<N; i++) v[i]=rand()*0xFFFF + rand();
76      printf("\nOrdinamento di un vettore di %d elementi in corso ...",N);
77      start = clock();
78      //Ordina il vettore
79      sort(v,0,N-1);
80      end = clock();
81      cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
82      printf("\nTempo di CPU utilizzato: %lf secondi.\n", cpu_time_used) ;
83      return 0;
84  }