current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 2 down vote favorite

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;
}
share|improve this question
6  
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 Dec 14 '14 at 23:53

1 Answer 1

up vote 5 down vote

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--;
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.