/*
* Experiments with various sorting algorithms
*
- * (c) 2007 Martin Mares <mj@ucw.cz>
+ * (c) 2007--2008 Martin Mares <mj@ucw.cz>
*/
#include "sherlock/sherlock.h"
#define ASORT_ELT(i) a[i].key
#define ASORT_SWAP(i,j) do { struct elt t=a[i]; a[i]=a[j]; a[j]=t; } while (0)
#define ASORT_EXTRA_ARGS , struct elt *a
-#include "ucw/arraysort.h"
+#include "ucw/sorter/array-simple.h"
#define ASORT_PREFIX(x) asi_##x
#define ASORT_KEY_TYPE u32
#define ASORT_ELT(i) ind[i]->key
#define ASORT_SWAP(i,j) do { struct elt *t=ind[i]; ind[i]=ind[j]; ind[j]=t; } while (0)
-#include "ucw/arraysort.h"
+#include "ucw/sorter/array-simple.h"
static void r1_sort(void)
{
uns nn = n;
while (nn)
HEAP_DELMIN(struct elt, heap, nn, H_LESS, HEAP_SWAP);
+#undef H_LESS
+}
+
+static void heapsort_ind(void)
+{
+#define H_LESS(_a,_b) ((_a)->key > (_b)->key)
+ struct elt **heap = ind-1;
+ HEAP_INIT(struct elt *, heap, n, H_LESS, HEAP_SWAP);
+ uns nn = n;
+ while (nn)
+ HEAP_DELMIN(struct elt *, heap, nn, H_LESS, HEAP_SWAP);
+#undef H_LESS
}
static void mk_ary(void)
for (uns i=0; i<n; i++)
array0[i] = array1[i] = (struct elt) { 0 };
+ log(L_INFO, "Testing with %u elements", n);
+
mk_ary();
timestamp_t timer;
init_timer(&timer);
BENCH(ary, "samplesort", samplesort());
BENCH(ary, "samplesort2", samplesort2());
BENCH(ary, "heapsort", heapsort());
+ BENCH(ind, "indirect heapsort", heapsort_ind());
free_elts(array0, n);
free_elts(array1, n);