Debian Codegraph @

libsrc/math/heapsort.c

raw
1 /*===========================================================================
2 Copyright (C) 1995-2015 European Southern Observatory (ESO)
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 as
6 published by the Free Software Foundation; either version 2 of
7 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
15 License along with this program; if not, write to the Free
16 Software Foundation, Inc., 675 Massachusetss Ave, Cambridge,
17 MA 02139, USA.
18
19 Corresponding concerning ESO-MIDAS should be addressed as follows:
20 Internet e-mail: [email protected]
21 Postal address: European Southern Observatory
22 Data Management Division
23 Karl-Schwarzschild-Strasse 2
24 D 85748 Garching bei Muenchen
25 GERMANY
26 ===========================================================================*/
27
28 #include "mutil.h"
29
30 #include <stdio.h>
31 #include <time.h>
32 #include <string.h>
33 #include <stdlib.h>
34
35
36 long int GetTickCount();
37 double GetDuration(long int t1, long int t2);
38
39 /* Validation code */
40 #ifdef VALIDATE_CODE
41 #define NUM_ITEMS 10
42
43 float flt_numbers[NUM_ITEMS];
44 int int_numbers[NUM_ITEMS];
45 int rank[NUM_ITEMS];
46
47 int main(void)
48 {
49 int i;
50 long t, tt;
51 double dur;
52
53 //seed random number generator
54 srand(GetTickCount());
55
56 //fill array with random integers
57 for (i = 0; i < NUM_ITEMS; i++) {
58 int_numbers[i] = rand()%NUM_ITEMS;
59 flt_numbers[i] = (float)rand()/1000.;
60 }
61
62 printf("Starting with Integer Heap sort.\n");
63 for (i = 0; i < NUM_ITEMS; i++)
64 printf("[%d]=%i,%f ", rank[i], int_numbers[i], flt_numbers[i]);
65 printf("\n");
66
67 //perform heap sort on integer array
68 tt = GetTickCount();
69 heapSortInt(NUM_ITEMS, int_numbers, rank);
70 t = GetTickCount();
71 dur = GetDuration(tt, t);
72
73 printf("Done with Integer Heap sort. %d items %lf sec\n",NUM_ITEMS,dur);
74 for (i = 0; i < NUM_ITEMS; i++)
75 printf("[%d]=%i ", rank[i],int_numbers[i]);
76 printf("\n");
77
78 printf("Starting with Float Heap sort.\n");
79 //perform heap sort on float array
80 tt = GetTickCount();
81 heapSortFloat(NUM_ITEMS, flt_numbers, rank);
82 t = GetTickCount();
83 dur = GetDuration(tt, t);
84
85 printf("Done with Float Heap sort. %d items %lf sec\n",NUM_ITEMS,dur);
86
87 for (i = 0; i < NUM_ITEMS; i++)
88 printf("[%d]=%f ", rank[i],flt_numbers[i]);
89 printf("\n");
90
91 {
92 int n = 9;
93 int i;
94 float *flt_numbers = malloc(n * sizeof(float));
95 int *rank = malloc(n * sizeof(int));
96
97 flt_numbers[0]=0.002437;
98 flt_numbers[1]=0.002441;
99 flt_numbers[2]=0.002430;
100 flt_numbers[3]=0.002438;
101 flt_numbers[4]=0.002461;
102 flt_numbers[5]=0.002463;
103 flt_numbers[6]=0.002413;
104 flt_numbers[7]=0.002451;
105 flt_numbers[8]=0.002467;
106 heapSortFloat(n, flt_numbers, rank);
107 printf("i rank flt\n");
108 printf("%i: %i %f\n", 0, rank[0], flt_numbers[0]);
109 for (i = 1; i < n; i++) {
110 printf("%i: %i %f%s\n", i, rank[i], flt_numbers[i],
111 (flt_numbers[i-1] > flt_numbers[i])?" (not in order)":"");
112 if (flt_numbers[i-1] > flt_numbers[i])
113 abort();
114 }
115 free(flt_numbers);
116 free(rank);
117 }
118
119 return 0;
120
121 }
122 #endif
123
124 #define MIDAS_TOOLS_SORT_LT(a, b) ((a) < (b))
125 #define MIDAS_INT_SWAP(a,b) { const int t=(a); (a)=(b); (b)=t; }
126
127 #define CONCAT(a,b) a ## b
128 #define CONCAT2X(a,b) CONCAT(a,b)
129 #define ADDTYPE(a) CONCAT2X(a, MIDAS_TYPE_NAME)
130
131 #define MIDAS_TYPE_NAME Int
132 #define MIDAS_TYPE int
133 #include "heapsort.h"
134 #undef MIDAS_TYPE_NAME
135 #undef MIDAS_TYPE
136
137 #define MIDAS_TYPE_NAME Float
138 #define MIDAS_TYPE float
139 #include "heapsort.h"
140 #undef MIDAS_TYPE_NAME
141 #undef MIDAS_TYPE
142
143 #define MIDAS_TYPE_NAME Double
144 #define MIDAS_TYPE double
145 #include "heapsort.h"
146 #undef MIDAS_TYPE_NAME
147 #undef MIDAS_TYPE
148
149 long int GetTickCount() {
150 clock_t t2 = clock();
151 return((long int) t2);
152 }
153
154 double GetDuration(long int t1, long int t2) {
155 double dur = 1000.0*(t2-t1)/CLOCKS_PER_SEC;
156 return(dur);
157 }