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