#include <stdlib.h>
#include <stdio.h>

#define CMP(a,b) ((a==b)?0:(a<b)?-1:1)
#define uint32 int
#define ARRAY_SIZE 100

int my_array[ARRAY_SIZE];

void ArraySort(int This[], uint32 the_len)
{
/* heap sort */

uint32 half;
uint32 parent;

if (the_len <= 1)
return;

half = the_len >> 1;
for (parent = half; parent >= 1; --parent)
{
    int temp;
    int level = 0;
    uint32 child;

child = parent;
/* bottom-up downheap */

    /* leaf-search for largest child path */
    while (child <= half)
    {
      ++level;
      child += child;
      if ((child < the_len) &&
          (CMP(This[child], This[child - 1]) > 0))
        ++child;
    }
    /* bottom-up-search for rotation point */
    temp = This[parent - 1];
    for (;;)
    {
      if (parent == child)
        break;
      if (CMP(temp, This[child - 1]) <= 0)
        break;
      child >>= 1;
      --level;
    }
    /* rotate nodes from parent to rotation point */
    for (;level > 0; --level)
    {
      This[(child >> level) - 1] =
        This[(child >> (level - 1)) - 1];
    }
    This[child - 1] = temp;
}

--the_len;
do
{
    int temp;
    int level = 0;
    uint32 child;

    /* move max element to back of array */
    temp = This[the_len];
    This[the_len] = This[0];
    This[0] = temp;

child = parent = 1;
half = the_len >> 1;

/* bottom-up downheap */

    /* leaf-search for largest child path */
    while (child <= half)
    {
      ++level;
      child += child;
      if ((child < the_len) &&
          (CMP(This[child], This[child - 1]) > 0))
        ++child;
    }
    /* bottom-up-search for rotation point */
    for (;;)
    {
      if (parent == child)
        break;
      if (CMP(temp, This[child - 1]) <= 0)
        break;
      child >>= 1;
      --level;
    }
    /* rotate nodes from parent to rotation point */
    for (;level > 0; --level)
    {
      This[(child >> level) - 1] =
        This[(child >> (level - 1)) - 1];
    }
    This[child - 1] = temp;
} while (--the_len >= 1);
}

void fill_array()
{
int indx;

for (indx=0; indx < ARRAY_SIZE; ++indx)
{
my_array[indx] = rand();
}
}

int main()
{
int indx;

fill_array();

ArraySort(my_array, ARRAY_SIZE);

for (indx=1; indx < ARRAY_SIZE; ++indx) {
    if (my_array[indx - 1] > my_array[indx]) {
      printf("bad sort\n");
      return(1);
    } else {
      printf("%d, ",my_array[indx-1]);
    }
}
return(0);
}

back