diff options
| author | wolfbeast <mcwerewolf@wolfbeast.com> | 2019-03-29 16:04:01 +0100 |
|---|---|---|
| committer | wolfbeast <mcwerewolf@wolfbeast.com> | 2019-03-29 16:04:01 +0100 |
| commit | 88083f8c683c18f4de68a20c863a82a9da65db8f (patch) | |
| tree | 926656892d9d80260da02ea8ea71031b140c51df /other-licenses/7zstub/src/C/Sort.c | |
| parent | f999f544aad04069b03704d994a99352263f600b (diff) | |
| parent | 843e4ceffd6ce21a6e6db37419335eafdc543e18 (diff) | |
| download | UXP-88083f8c683c18f4de68a20c863a82a9da65db8f.tar UXP-88083f8c683c18f4de68a20c863a82a9da65db8f.tar.gz UXP-88083f8c683c18f4de68a20c863a82a9da65db8f.tar.lz UXP-88083f8c683c18f4de68a20c863a82a9da65db8f.tar.xz UXP-88083f8c683c18f4de68a20c863a82a9da65db8f.zip | |
Merge branch 'master' into Sync-weave
Diffstat (limited to 'other-licenses/7zstub/src/C/Sort.c')
| -rw-r--r-- | other-licenses/7zstub/src/C/Sort.c | 141 |
1 files changed, 141 insertions, 0 deletions
diff --git a/other-licenses/7zstub/src/C/Sort.c b/other-licenses/7zstub/src/C/Sort.c new file mode 100644 index 000000000..73dcbf059 --- /dev/null +++ b/other-licenses/7zstub/src/C/Sort.c @@ -0,0 +1,141 @@ +/* Sort.c -- Sort functions
+2014-04-05 : Igor Pavlov : Public domain */
+
+#include "Precomp.h"
+
+#include "Sort.h"
+
+#define HeapSortDown(p, k, size, temp) \
+ { for (;;) { \
+ size_t s = (k << 1); \
+ if (s > size) break; \
+ if (s < size && p[s + 1] > p[s]) s++; \
+ if (temp >= p[s]) break; \
+ p[k] = p[s]; k = s; \
+ } p[k] = temp; }
+
+void HeapSort(UInt32 *p, size_t size)
+{
+ if (size <= 1)
+ return;
+ p--;
+ {
+ size_t i = size / 2;
+ do
+ {
+ UInt32 temp = p[i];
+ size_t k = i;
+ HeapSortDown(p, k, size, temp)
+ }
+ while (--i != 0);
+ }
+ /*
+ do
+ {
+ size_t k = 1;
+ UInt32 temp = p[size];
+ p[size--] = p[1];
+ HeapSortDown(p, k, size, temp)
+ }
+ while (size > 1);
+ */
+ while (size > 3)
+ {
+ UInt32 temp = p[size];
+ size_t k = (p[3] > p[2]) ? 3 : 2;
+ p[size--] = p[1];
+ p[1] = p[k];
+ HeapSortDown(p, k, size, temp)
+ }
+ {
+ UInt32 temp = p[size];
+ p[size] = p[1];
+ if (size > 2 && p[2] < temp)
+ {
+ p[1] = p[2];
+ p[2] = temp;
+ }
+ else
+ p[1] = temp;
+ }
+}
+
+void HeapSort64(UInt64 *p, size_t size)
+{
+ if (size <= 1)
+ return;
+ p--;
+ {
+ size_t i = size / 2;
+ do
+ {
+ UInt64 temp = p[i];
+ size_t k = i;
+ HeapSortDown(p, k, size, temp)
+ }
+ while (--i != 0);
+ }
+ /*
+ do
+ {
+ size_t k = 1;
+ UInt64 temp = p[size];
+ p[size--] = p[1];
+ HeapSortDown(p, k, size, temp)
+ }
+ while (size > 1);
+ */
+ while (size > 3)
+ {
+ UInt64 temp = p[size];
+ size_t k = (p[3] > p[2]) ? 3 : 2;
+ p[size--] = p[1];
+ p[1] = p[k];
+ HeapSortDown(p, k, size, temp)
+ }
+ {
+ UInt64 temp = p[size];
+ p[size] = p[1];
+ if (size > 2 && p[2] < temp)
+ {
+ p[1] = p[2];
+ p[2] = temp;
+ }
+ else
+ p[1] = temp;
+ }
+}
+
+/*
+#define HeapSortRefDown(p, vals, n, size, temp) \
+ { size_t k = n; UInt32 val = vals[temp]; for (;;) { \
+ size_t s = (k << 1); \
+ if (s > size) break; \
+ if (s < size && vals[p[s + 1]] > vals[p[s]]) s++; \
+ if (val >= vals[p[s]]) break; \
+ p[k] = p[s]; k = s; \
+ } p[k] = temp; }
+
+void HeapSortRef(UInt32 *p, UInt32 *vals, size_t size)
+{
+ if (size <= 1)
+ return;
+ p--;
+ {
+ size_t i = size / 2;
+ do
+ {
+ UInt32 temp = p[i];
+ HeapSortRefDown(p, vals, i, size, temp);
+ }
+ while (--i != 0);
+ }
+ do
+ {
+ UInt32 temp = p[size];
+ p[size--] = p[1];
+ HeapSortRefDown(p, vals, 1, size, temp);
+ }
+ while (size > 1);
+}
+*/
|