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;
}

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. — JS1
– JS1, Commented Dec 14, 2014 at 23:53

score 5 · Accepted Answer · 2015-05-10 17:15:55Z

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--;
}

Stack Exchange Network

A different implementation of Heap Sort

1 Answer 1

You must log in to answer this question.

Hot Network Questions

A different implementation of Heap Sort

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions