nel/3rdparty/seven_zip/Sort.c

   1 /* Sort.c -- Sort functions
   2 2014-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
  17 void 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
  63 void 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
 119 void 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 */