heapsort.c

#include <stdio.h>
#include <stdlib.h>
/*
  This is an example function using an array of ints.
  To use an array of coords, you'll need to modify the gt() function
  and update the type of 'arr' in the popheap(), heapify(), and
  heapsort() functions.

  Call heapsort() by passing in the array to sort and its size
  WARNING: This will sort in-place. It changes the original array passed to it.
*/
int gt(int x,int y){return x<y;}
void popheap(int* arr,int size){
//I'll never call this if arr is NULL or size 0
  int x=arr[0];
  int k=0;
  int i;
  //I've saved arr[0], now I need to shift the biggest elements up
  while(k<size){
    i=k*2+1;
    if(i<size){
      if(i+1<size){i+=gt(arr[i],arr[i+1]);}
      arr[k]=arr[i];
    }
    k=i;
  }
  arr[i>>1]=arr[size-1];
  arr[size-1]=x;
  return;
}
void heapify(int* arr,int size){
  if(size<2){return;}
  int n=(size-1)>>1;
  int m=n*2+1;
  int i,j,k;
  //Optimizing first iteration, since that's the only one that needs to verify bounds
  if(m+1==size){i=m;} else {i=m+gt(arr[m],arr[m+1]);};
  if(gt(arr[n],arr[i])){j=arr[n];arr[n]=arr[i];arr[i]=j;}
  n--;
  m-=2;
  while(n>=0){
    i=m+gt(arr[m],arr[m+1]);
    if(gt(arr[n],arr[i])){
      j=arr[n];arr[n]=arr[i];arr[i]=j;
      //but now I have to propogate changes up through the tree
      //have to check 2i+1 and 2i+2
      k=i*2+1;
      while(k<size){
        if(k+1!=size){k+=gt(arr[k],arr[k+1]);};
        if(gt(arr[i],arr[k])){
          j=arr[i];arr[i]=arr[k];arr[k]=j;
          i=k;
          k=k*2+1;} else {k=size;}
      }
    }
    n--;
    m-=2;
  }
  return;
}
int* heapsort(int* arr,int size){
  if(!arr){return arr;}
  heapify(arr,size);
  for(int i=size;i>1;i--){    //omitting i=0 since it's the last item, so of course it will be the smallest of all remaining items
    popheap(arr,i);
  }
  return arr;
}
int main(){
  int arr[8]={7,2,9,3,1,8,6,5};
  int* heap=heapsort(arr,8);
  for(int i;i<8;i++){printf("%d\n",heap[i]);}
  return 0;
}