summaryrefslogtreecommitdiff
path: root/h/sort.h
diff options
context:
space:
mode:
Diffstat (limited to 'h/sort.h')
-rw-r--r--h/sort.h62
1 files changed, 62 insertions, 0 deletions
diff --git a/h/sort.h b/h/sort.h
new file mode 100644
index 0000000..98bee8f
--- /dev/null
+++ b/h/sort.h
@@ -0,0 +1,62 @@
+
+/*
+ * Copyright 1996 - 2010 Graeme W. Gill
+ * All rights reserved.
+ *
+ * This material is licenced under the GNU GENERAL PUBLIC LICENSE Version 2 or later :-
+ * see the License2.txt file for licencing details.
+ */
+
+/*
+ * Heapsort macro - sort smallest to largest.
+ * Heapsort is guaranteed nlogn, doesn't need any
+ * extra storage, but often isn't as fast as quicksort.
+ */
+
+/* Need to #define HEAP_COMPARE(A,B) so it returns true if A < B */
+/* Note that A will be ARRAY[a], and B will be ARRAY[b] where a and b are indexes. */
+/* TYPE should be the type of each entry of the ARRAY */
+#define HEAPSORT(TYPE,ARRAY,NUMBER) \
+ { \
+ TYPE *hs_ncb = ARRAY; \
+ int hs_l,hs_j,hs_ir,hs_i; \
+ TYPE hs_rra; \
+ \
+ if (NUMBER >= 2) \
+ { \
+ hs_l = NUMBER >> 1; \
+ hs_ir = NUMBER-1; \
+ for (;;) \
+ { \
+ if (hs_l > 0) \
+ hs_rra = hs_ncb[--hs_l]; \
+ else \
+ { \
+ hs_rra = hs_ncb[hs_ir]; \
+ hs_ncb[hs_ir] = hs_ncb[0]; \
+ if (--hs_ir == 0) \
+ { \
+ hs_ncb[0] = hs_rra; \
+ break; \
+ } \
+ } \
+ hs_i = hs_l; \
+ hs_j = hs_l+hs_l+1; \
+ while (hs_j <= hs_ir) \
+ { \
+ if (hs_j < hs_ir && HEAP_COMPARE(hs_ncb[hs_j],hs_ncb[hs_j+1])) \
+ hs_j++; \
+ if (HEAP_COMPARE(hs_rra,hs_ncb[hs_j])) \
+ { \
+ hs_ncb[hs_i] = hs_ncb[hs_j]; \
+ hs_i = hs_j; \
+ hs_j = hs_j+hs_j+1; \
+ } \
+ else \
+ hs_j = hs_ir + 1; \
+ } \
+ hs_ncb[hs_i] = hs_rra; \
+ } \
+ } \
+ }
+