Heapsort algorithm CLRS

Question

I was implementing a heapsort algorithm in C according to CLRS. However I am unable to get a sorted output. Can you please have a look and tell what is wrong with my code. Functions maxheap and buildmaxheap works. I am not able to figure what is wrong with the code.

The code is supposed to heapsort the array elements. I feel there is an error in the heapsort() function as the maxheap and buildmaxheap work just fine.

The final output I am getting is

1 1 1 1 2 1 2 2 1 1

But the expected output should be

1 2 3 4 7 8 9 10 14 16

The code:

#include<stdlib.h>
#include<stdio.h>

#define maxn 11
int n=10;

int parent(int i)
{
    return i/2;
}

int left(int i)
{
    return 2*i+0;
}

int right(int i)
{
    return 2*i+1+0;
}

void  max_heap(int x[],int i,int heapsize)
{
    int largest;
    int l=left(i);
    int r=right(i);

    if (l<=heapsize &&  x[l]>x[i]){
        largest=l;
    }
    else
    {
        largest=i;
    }
    if (r<=heapsize && x[r]>x[largest]){
        largest=r;
    }
    if (largest!=i)
    {
        int s=x[i];x[i]=x[largest];x[largest]=s;
        max_heap(x,largest,heapsize);
    }
}

void buildmaxheap(int x[],int heapsize)
{

    int i;
    for(i=5;i>=1;i--)
        max_heap(x,i,heapsize);

}

void heapsort(int x[])
{
    buildmaxheap(x,10);
    int i,t,heapsize=10;
    for(i=10;i>=2;i--)
    {
        int s=x[i];x[1]=x[i];x[i]=s;

        heapsize--;
        /*
         printf("%d",heapsize);
         */
        max_heap(x,i,heapsize);
    }
    for(i=1;i<=10;i++)
        printf("%d\t",x[i]);

}

int main()
{
    int x[maxn],i;
    x[1]=16;
    x[2]=4;
    x[3]=10;
    x[4]=14;
    x[5]=7;
    x[6]=9;
    x[7]=3;
    x[8]=2;
    x[9]=8;
    x[10]=1;
    heapsort(x);
    /*
     for(i=1;i<=10;i++)
     printf("%d\t",x[i]);
     */
}

Answer 1

There's a lack of logic in heapsort. Any sort algorithm has to compare 2 values and do one thing for less than, another for greater and leave well alone if the same. At present you automatically swap a comparator with index 1 multiple times.

I can't clearly see why it's loosing numbers resulting in random 1's and 2's, but it looks so broken that I'm not giving anymore time until you try again.

In c the array index begin from 0, don't avoid it in this little 10 node quandary it's nothing much. But if you don't start to automatically consider zero to be first you will pay big time.

Answer 2

This line:

int s=x[i];x[1]=x[i];x[i]=s;

looks like it's trying to do a swap, but it's mixed up. Look at the indexes and think about the order.

After you fix that, there's still another bug. I don't have the book so I don't know exactly what it told you to do, but I believe you need to fix up the heap property starting from the root after you remove an element, and your code doesn't do that.