diff options
author | Jörg Frings-Fürst <debian@jff-webhosting.net> | 2014-09-01 13:56:46 +0200 |
---|---|---|
committer | Jörg Frings-Fürst <debian@jff-webhosting.net> | 2014-09-01 13:56:46 +0200 |
commit | 22f703cab05b7cd368f4de9e03991b7664dc5022 (patch) | |
tree | 6f4d50beaa42328e24b1c6b56b6ec059e4ef21a5 /h/sort.h |
Initial import of argyll version 1.5.1-8debian/1.5.1-8
Diffstat (limited to 'h/sort.h')
-rw-r--r-- | h/sort.h | 62 |
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; \ + } \ + } \ + } + |