Mercurial > vba-linux

     1 /* Sort.c -- Sort functions

     2 2008-08-17

     3 Igor Pavlov

     4 Public domain */

     5 

     6 #include "Sort.h"

     7 

     8 #define HeapSortDown(p, k, size, temp) \

     9   { for (;;) { \

    10     UInt32 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, UInt32 size)

    18 {

    19   if (size <= 1)

    20     return;

    21   p--;

    22   {

    23     UInt32 i = size / 2;

    24     do

    25     {

    26       UInt32 temp = p[i];

    27       UInt32 k = i;

    28       HeapSortDown(p, k, size, temp)

    29     }

    30     while (--i != 0);

    31   }

    32   /*

    33   do

    34   {

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

    64 #define HeapSortRefDown(p, vals, n, size, temp) \

    65   { UInt32 k = n; UInt32 val = vals[temp]; for (;;) { \

    66     UInt32 s = (k << 1); \

    67     if (s > size) break; \

    68     if (s < size && vals[p[s + 1]] > vals[p[s]]) s++; \

    69     if (val >= vals[p[s]]) break; \

    70     p[k] = p[s]; k = s; \

    71   } p[k] = temp; }

    72 

    73 void HeapSortRef(UInt32 *p, UInt32 *vals, UInt32 size)

    74 {

    75   if (size <= 1)

    76     return;

    77   p--;

    78   {

    79     UInt32 i = size / 2;

    80     do

    81     {

    82       UInt32 temp = p[i];

    83       HeapSortRefDown(p, vals, i, size, temp);

    84     }

    85     while (--i != 0);

    86   }

    87   do

    88   {

    89     UInt32 temp = p[size];

    90     p[size--] = p[1];

    91     HeapSortRefDown(p, vals, 1, size, temp);

    92   }

    93   while (size > 1);

    94 }

    95 */
author	Robert McIntyre <rlm@mit.edu>
date	Sat, 03 Mar 2012 10:31:27 -0600
parents
children