Home | History | Annotate | Download | only in 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 */
    142