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 }