release/src/lzma/C/Sort.c

   1 /* Sort.c */
   2
   3 #include "Sort.h"
   4
   5 #define HeapSortDown(p, k, size, temp) \
   6   { for (;;) { \
   7     UInt32 s = (k << 1); \
   8     if (s > size) break; \
   9     if (s < size && p[s + 1] > p[s]) s++; \
  10     if (temp >= p[s]) break; \
  11     p[k] = p[s]; k = s; \
  12   } p[k] = temp; }
  13
  14 void HeapSort(UInt32 *p, UInt32 size)
  15 {
  16   if (size <= 1)
  17     return;
  18   p--;
  19   {
  20     UInt32 i = size / 2;
  21     do
  22     {
  23       UInt32 temp = p[i];
  24       UInt32 k = i;
  25       HeapSortDown(p, k, size, temp)
  26     }
  27     while(--i != 0);
  28   }
  29   /*
  30   do
  31   {
  32     UInt32 k = 1;
  33     UInt32 temp = p[size];
  34     p[size--] = p[1];
  35     HeapSortDown(p, k, size, temp)
  36   }
  37   while (size > 1);
  38   */
  39   while (size > 3)
  40   {
  41     UInt32 temp = p[size];
  42     UInt32 k = (p[3] > p[2]) ? 3 : 2;
  43     p[size--] = p[1];
  44     p[1] = p[k];
  45     HeapSortDown(p, k, size, temp)
  46   }
  47   {
  48     UInt32 temp = p[size];
  49     p[size] = p[1];
  50     if (size > 2 && p[2] < temp)
  51     {
  52       p[1] = p[2];
  53       p[2] = temp;
  54     }
  55     else
  56       p[1] = temp;
  57   }
  58 }
  59
  60 /*
  61 #define HeapSortRefDown(p, vals, n, size, temp) \
  62   { UInt32 k = n; UInt32 val = vals[temp]; for (;;) { \
  63     UInt32 s = (k << 1); \
  64     if (s > size) break; \
  65     if (s < size && vals[p[s + 1]] > vals[p[s]]) s++; \
  66     if (val >= vals[p[s]]) break; \
  67     p[k] = p[s]; k = s; \
  68   } p[k] = temp; }
  69
  70 void HeapSortRef(UInt32 *p, UInt32 *vals, UInt32 size)
  71 {
  72   if (size <= 1)
  73     return;
  74   p--;
  75   {
  76     UInt32 i = size / 2;
  77     do
  78     {
  79       UInt32 temp = p[i];
  80       HeapSortRefDown(p, vals, i, size, temp);
  81     }
  82     while(--i != 0);
  83   }
  84   do
  85   {
  86     UInt32 temp = p[size];
  87     p[size--] = p[1];
  88     HeapSortRefDown(p, vals, 1, size, temp);
  89   }
  90   while (size > 1);
  91 }
  92 */