Advertisement
Zeda

heapsort.c

Aug 31st, 2018
672
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.00 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. /*
  4.   This is an example function using an array of ints.
  5.   To use an array of coords, you'll need to modify the gt() function
  6.   and update the type of 'arr' in the popheap(), heapify(), and
  7.   heapsort() functions.
  8.  
  9.   Call heapsort() by passing in the array to sort and its size
  10.   WARNING: This will sort in-place. It changes the original array passed to it.
  11. */
  12. int gt(int x,int y){return x<y;}
  13. void popheap(int* arr,int size){
  14. //I'll never call this if arr is NULL or size 0
  15.   int x=arr[0];
  16.   int k=0;
  17.   int i;
  18.   //I've saved arr[0], now I need to shift the biggest elements up
  19.   while(k<size){
  20.     i=k*2+1;
  21.     if(i<size){
  22.       if(i+1<size){i+=gt(arr[i],arr[i+1]);}
  23.       arr[k]=arr[i];
  24.     }
  25.     k=i;
  26.   }
  27.   arr[i>>1]=arr[size-1];
  28.   arr[size-1]=x;
  29.   return;
  30. }
  31. void heapify(int* arr,int size){
  32.   if(size<2){return;}
  33.   int n=(size-1)>>1;
  34.   int m=n*2+1;
  35.   int i,j,k;
  36.   //Optimizing first iteration, since that's the only one that needs to verify bounds
  37.   if(m+1==size){i=m;} else {i=m+gt(arr[m],arr[m+1]);};
  38.   if(gt(arr[n],arr[i])){j=arr[n];arr[n]=arr[i];arr[i]=j;}
  39.   n--;
  40.   m-=2;
  41.   while(n>=0){
  42.     i=m+gt(arr[m],arr[m+1]);
  43.     if(gt(arr[n],arr[i])){
  44.       j=arr[n];arr[n]=arr[i];arr[i]=j;
  45.       //but now I have to propogate changes up through the tree
  46.       //have to check 2i+1 and 2i+2
  47.       k=i*2+1;
  48.       while(k<size){
  49.         if(k+1!=size){k+=gt(arr[k],arr[k+1]);};
  50.         if(gt(arr[i],arr[k])){
  51.           j=arr[i];arr[i]=arr[k];arr[k]=j;
  52.           i=k;
  53.           k=k*2+1;} else {k=size;}
  54.       }
  55.     }
  56.     n--;
  57.     m-=2;
  58.   }
  59.   return;
  60. }
  61. int* heapsort(int* arr,int size){
  62.   if(!arr){return arr;}
  63.   heapify(arr,size);
  64.   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
  65.     popheap(arr,i);
  66.   }
  67.   return arr;
  68. }
  69. int main(){
  70.   int arr[8]={7,2,9,3,1,8,6,5};
  71.   int* heap=heapsort(arr,8);
  72.   for(int i;i<8;i++){printf("%d\n",heap[i]);}
  73.   return 0;
  74. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement