C/Sort.c

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