diff options
Diffstat (limited to 'test/monniaux/quicksort/quicksort.c')
-rw-r--r-- | test/monniaux/quicksort/quicksort.c | 42 |
1 files changed, 42 insertions, 0 deletions
diff --git a/test/monniaux/quicksort/quicksort.c b/test/monniaux/quicksort/quicksort.c new file mode 100644 index 00000000..de04bf2d --- /dev/null +++ b/test/monniaux/quicksort/quicksort.c @@ -0,0 +1,42 @@ +#include "quicksort.h" + +/* Rosetta Code */ +void quicksort(data *A, int len) { + if (len < 2) return; + + data pivot = A[len / 2]; + + int i, j; + for (i = 0, j = len - 1; ; i++, j--) { + while (A[i] < pivot) i++; + while (A[j] > pivot) j--; + + if (i >= j) break; + + data temp = A[i]; + A[i] = A[j]; + A[j] = temp; + } + + quicksort(A, i); + quicksort(A + i, len - i); +} + +data data_random(void) { + static uint64_t next = 1325997111; + next = next * 1103515245 + 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; +} |