A different implementation of Heap Sort

Question

The following implementation is a bit different form the standard implementations I have read. Is it correct?

#include <malloc.h>
#include <stdio.h>
void heapify(int[],int,int);
void swap(int a[],int i,int j){
 int temp=a[i];
 a[i]=a[j];
 a[j]=temp;
}
void heap_sort(int a[],int l,int r){
 for(int i=l;i<r;i++)
 heapify(a,l,r);
}
void heapify(int a[],int l,int r){//brings largest element to position l
 int size=(r-l+1);
 int i=size-1,larger;
 if(size%2){
 if(a[l+i]<a[l+i/2])
 swap(a,l+i,l+i/2);
 i--;}
 while(i>0){
 if(a[l+i]>a[l+i-1])
 larger=l+i-1;
 else
 larger=l+i;
 if(a[l+(i-1)/2]>a[larger])
 swap(a,larger,l+(i-1)/2);
 i-=2;
 }
}
void printArray(int arr[], int n)
{
 int i;
 for (i=0; i < n; i++)
 printf("%d ", arr[i]);
 printf("\n");
}
/* Driver program to test insertion sort */
int main()
{
 int arr[] = {12, 11, 13, 5, 6, 7};
 int arr_size = sizeof(arr)/sizeof(arr[0]);
 printf("Given array is \n");
 printArray(arr, arr_size);
 heap_sort(arr,0,arr_size-1);
 printf("\nSorted array is \n");
 printArray(arr, arr_size);
 return 0;
 return 0;
}

• JS1: It looks like it will sort the array but it behaves more like a bubble sort than a heap sort. It appears to be an O(N^2) algorithm so I wouldn't really call it a "heap sort", even though it uses a heap.

Answer 1

You have no extra spacing between functions except before the main() function, which has several returns. I would put a single return between each function to make it clear where they begin and end without even looking.

---

You use spaces between variables and operators inconsistently, and you should be consistent:

printArray(arr, arr_size);
heap_sort(arr,0,arr_size-1);
for (i=0; i < n; i++)

There are others as well. I would recommend using a space for readability.

I would put spaces around variables in function definitions as well:

void heapify(int[],int,int);

---

You don't need two return 0;s at the end of main().

---

While not absolutely necessary, it might help prevent bugs if you use braces around one-line ifs and loops:

for (i=0; i < n; i++)
 printf("%d ", arr[i]);

---

Your brace style here is rather peculiar:

if(size%2){
 if(a[l+i]<a[l+i/2])
 swap(a,l+i,l+i/2);
 i--;}

That final brace should be written on the line below. I would use more spaces and braces as well:

if(size % 2) {
 if(a[l + i] < a[l + i / 2]) {
 swap(a, l + i, l + i / 2);
 }
 i--;
}