heapsort.c

#include <stdio.h>

#define DATA_SIZE 100000
#define STRINGS_SIZE 32
#define SWAP(a, b) {                            \
  int tmp;                                      \
  tmp = a;                                      \
  a = b;                                        \
  b = tmp;                                      \
  }

int heap_sort(int *, int);
int heap(int *, int);
int heap_recursive(int *, int);
int heap_swap(int *, int, int);

int
main (void)
{
  int i = 0;
  int length;
  int data[DATA_SIZE] = {0};
  char str[STRINGS_SIZE];
  FILE *fp;

  if ((fp = fopen("100.txt", "r")) == NULL) {
    puts("file open error.");
    return 1;
  }

  while (fgets(str, STRINGS_SIZE, fp) != NULL) {
    data[i] = atoi(str);
    i++;
  }

  length = i-1;
  heap_sort(data, length);

  for (i = 0; i <= length; i++) {
    printf("%d, ", data[i]);
  }
  putchar('\n');

  return 0;
}

int
heap_sort (int *a, int last)
{
  int i, j;
  for (i = last; i > 0; i--) {
    heap(a, i);
    SWAP(a[0], a[i]);
  }
  return 0;
}

int
heap(int *a, int last)
{
  return heap_recursive(a, last);
}

int
heap_recursive(int *a, int last)
{
  int i, next = last-1;

  while((i = heap_swap(a, last/2, last)) != 0);
  return ((next <= 0) ? a[1] : heap_recursive(a, next));
}

int
heap_swap(int *a, int i, int last)
{
  int j = i*2;

  if (j+1 > last || (a[i] >= a[j] && a[i] >= a[j+1])) return 0;
  if (j < last && a[j] < a[j+1]) j++;
  if (a[i] < a[j]) SWAP(a[i], a[j]);

  return j;
}