implementation of Cormen's HeapSort algorithm in C

Question

I am trying to implement the Heap sort algorithm provided in Cormen. My code is as follows :

    #include<stdio.h>
    #include<conio.h>
    void max_heapify(int *,int);
    void build_max_heap(int *,int);
    void heapsort(int *,int);
    void swap(int,int);
    int heapsize;
    int main()
    {
            int *arr,n,i;
            printf("Enter no. of elements = ");
            scanf("%d",&n);
            arr=(int *)malloc(sizeof(int)*n);
            for(i=0;i<n;i++)
            {
             printf("Enter array elements = ");
             scanf("%d",&arr[i]);
            }
            //heapsize = n;
            heapsort(arr,n);
            printf("\nAfter heapsort \n");
            for(i=0;i<n;i++)
            {
                printf("%d  ",arr[i]);
            }
        return 0;
    }
 void heapsort(int *arr,int len)
 {
   int i;
   build_max_heap(arr,len);
    for(i= len-1;i>=1;i--)
    {
        swap(&arr[0],&arr[i]);
        heapsize = heapsize -1;
        max_heapify(arr,0);
    }
 }
void max_heapify(int *arr,int i)
{
    int l=2*i,r=2*i+1,largest;
    if(l<heapsize && arr[l]>arr[i])
        largest = l;
    else
        largest = i;
    if(r<heapsize && arr[r]>arr[largest])
        largest = r;

    if(largest != i)
    {
        swap(&arr[i],&arr[largest]);
        max_heapify(arr,largest);
    }
     }
void build_max_heap(int *arr,int len)
{
    heapsize = len;
    int i;
    for(i =len/2;i>=0;i--)
    {
        max_heapify(arr,i);
    }
}
void swap(int *a ,int *b)
{
    int temp = *a;
    *a= *b;
    *b= temp;
}

I cannot figure out what exactly is wrong in my code. The array is not getting sorted.In fact the original array is getting printed. Where am I going wrong?

Answer 1

1) Fix swap, you're passing by value. Which means after swap is called nothing was changed!

2) The max_heapify function is wrong. Your left and right child calculation is off by 1. When you swap, you swap an index with an array value, yikes.

3) heapsort for-loop is wrong. You should put the first element (largest one in the heap) to the last index of the current heap, decrease the size of heap so the last element is part of the sorted list and not the heap. Then you perculate down from the root, not from the last element. Should be:

 for(i= len-1;i>=1;i--)
   {
    swap(arr[0],arr[i]);
    heapsize = heapsize -1;
    max_heapify(arr,0);
   }

Answer 2

Your swapfunction takes the arguments by value. So the original values are copied and the copies are swapped instead of the originals.

swap( int *a, int *b)

Answer 3

You observe that your array is not getting sorted at all. Try working up to a complete heap sort in increments. So, as a debugging technique, create a copy of this code and replace the heapsort with a bubble sort. (bubble sorts are much easier to code). Get the bubble sort to work, this includes passing parameters and print the array before and after the sort.

Then do the heap sort.

Answer 4

The algorithm listed in Cormen seems to have a mistake. Simply change the following line in your code:

max_heapify(arr,0); \In heapsort function

with

build_max_heap(arr,heapsize);