1/* Sort.c -- Sort functions
22014-04-05 : Igor Pavlov : Public domain */
3
4#include "Precomp.h"
5
6#include "Sort.h"
7
8#define HeapSortDown(p, k, size, temp) \
9  { for (;;) { \
10    size_t s = (k << 1); \
11    if (s > size) break; \
12    if (s < size && p[s + 1] > p[s]) s++; \
13    if (temp >= p[s]) break; \
14    p[k] = p[s]; k = s; \
15  } p[k] = temp; }
16
17void HeapSort(UInt32 *p, size_t size)
18{
19  if (size <= 1)
20    return;
21  p--;
22  {
23    size_t i = size / 2;
24    do
25    {
26      UInt32 temp = p[i];
27      size_t k = i;
28      HeapSortDown(p, k, size, temp)
29    }
30    while (--i != 0);
31  }
32  /*
33  do
34  {
35    size_t k = 1;
36    UInt32 temp = p[size];
37    p[size--] = p[1];
38    HeapSortDown(p, k, size, temp)
39  }
40  while (size > 1);
41  */
42  while (size > 3)
43  {
44    UInt32 temp = p[size];
45    size_t k = (p[3] > p[2]) ? 3 : 2;
46    p[size--] = p[1];
47    p[1] = p[k];
48    HeapSortDown(p, k, size, temp)
49  }
50  {
51    UInt32 temp = p[size];
52    p[size] = p[1];
53    if (size > 2 && p[2] < temp)
54    {
55      p[1] = p[2];
56      p[2] = temp;
57    }
58    else
59      p[1] = temp;
60  }
61}
62
63void HeapSort64(UInt64 *p, size_t size)
64{
65  if (size <= 1)
66    return;
67  p--;
68  {
69    size_t i = size / 2;
70    do
71    {
72      UInt64 temp = p[i];
73      size_t k = i;
74      HeapSortDown(p, k, size, temp)
75    }
76    while (--i != 0);
77  }
78  /*
79  do
80  {
81    size_t k = 1;
82    UInt64 temp = p[size];
83    p[size--] = p[1];
84    HeapSortDown(p, k, size, temp)
85  }
86  while (size > 1);
87  */
88  while (size > 3)
89  {
90    UInt64 temp = p[size];
91    size_t k = (p[3] > p[2]) ? 3 : 2;
92    p[size--] = p[1];
93    p[1] = p[k];
94    HeapSortDown(p, k, size, temp)
95  }
96  {
97    UInt64 temp = p[size];
98    p[size] = p[1];
99    if (size > 2 && p[2] < temp)
100    {
101      p[1] = p[2];
102      p[2] = temp;
103    }
104    else
105      p[1] = temp;
106  }
107}
108
109/*
110#define HeapSortRefDown(p, vals, n, size, temp) \
111  { size_t k = n; UInt32 val = vals[temp]; for (;;) { \
112    size_t s = (k << 1); \
113    if (s > size) break; \
114    if (s < size && vals[p[s + 1]] > vals[p[s]]) s++; \
115    if (val >= vals[p[s]]) break; \
116    p[k] = p[s]; k = s; \
117  } p[k] = temp; }
118
119void HeapSortRef(UInt32 *p, UInt32 *vals, size_t size)
120{
121  if (size <= 1)
122    return;
123  p--;
124  {
125    size_t i = size / 2;
126    do
127    {
128      UInt32 temp = p[i];
129      HeapSortRefDown(p, vals, i, size, temp);
130    }
131    while (--i != 0);
132  }
133  do
134  {
135    UInt32 temp = p[size];
136    p[size--] = p[1];
137    HeapSortRefDown(p, vals, 1, size, temp);
138  }
139  while (size > 1);
140}
141*/
142