diff options
Diffstat (limited to 'test/monniaux/heapsort/heapsort.c')
-rw-r--r-- | test/monniaux/heapsort/heapsort.c | 58 |
1 files changed, 58 insertions, 0 deletions
diff --git a/test/monniaux/heapsort/heapsort.c b/test/monniaux/heapsort/heapsort.c new file mode 100644 index 00000000..550eff4d --- /dev/null +++ b/test/monniaux/heapsort/heapsort.c @@ -0,0 +1,58 @@ +#include "heapsort.h" + +/* Rosetta Code */ +static inline int max (data *a, int n, int i, int j, int k) { + int m = i; + if (j < n && a[j] > a[m]) { + m = j; + } + if (k < n && a[k] > a[m]) { + m = k; + } + return m; +} + +static void downheap (data *a, int n, int i) { + while (1) { + int j = max(a, n, i, 2 * i + 1, 2 * i + 2); + if (j == i) { + break; + } + data t = a[i]; + a[i] = a[j]; + a[j] = t; + i = j; + } +} + +void heapsort (data *a, int n) { + int i; + for (i = (n - 2) / 2; i >= 0; i--) { + downheap(a, n, i); + } + for (i = 0; i < n; i++) { + data t = a[n - i - 1]; + a[n - i - 1] = a[0]; + a[0] = t; + downheap(a, n - i - 1, 0); + } +} + +data data_random(void) { + static uint64_t next = 1325997111; + next = next * 1103515249 + 12345; + return next; +} + +void data_vec_random(data *a, unsigned len) { + for(unsigned i=0; i<len; i++) { + a[i] = data_random(); + } +} + +bool data_vec_is_sorted(const data *a, unsigned len) { + for(unsigned i=0; i<len-1; i++) { + if (a[i] > a[i+1]) return false; + } + return true; +} |