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*/