diff options
author | David Monniaux <david.monniaux@univ-grenoble-alpes.fr> | 2019-01-19 19:17:46 +0100 |
---|---|---|
committer | David Monniaux <david.monniaux@univ-grenoble-alpes.fr> | 2019-01-19 19:17:46 +0100 |
commit | 0fb339fd9dc30b997c76563271e9b3e3f24db84d (patch) | |
tree | 18e593d2fa17de903cc698b93176a1578fa89d6e /test/monniaux/heapsort/heapsort.c | |
parent | d70a9e55c3595cf7ee84ca9f3b1d5e272a5e3999 (diff) | |
download | compcert-kvx-0fb339fd9dc30b997c76563271e9b3e3f24db84d.tar.gz compcert-kvx-0fb339fd9dc30b997c76563271e9b3e3f24db84d.zip |
some more example
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; +} |