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