Monday 24 August 2015

Heapsort program in C

Before talking about heapsort I would prefer to talk about my terrible three-day-debugging story.
I thought of implementing heapsort function as qsort of C's standard library. 
I referred CLRS book for the algorithm. As it should work with any type of data, I needed to use void pointers to implement. Unfortunately, even when I followed algorithm clearly I got bad results during testing. I cross checked it again and again for three days but found no clue what was wrong with that. I figured out that I was doing something wrong while manipulating void pointers. I focused on void pointers usage; and while doing this I got a doubt : why qsort function takes size of each object when it is sufficient to have length of array to sort?
         Actually void specifies no type. So, like int it has no size specified. Then how can we expect incrementing void pointer with 1 will make it point to next object when we don't know the type of object it points to. During the debugging I found that incrementing a void pointer will make it to point next byte but not whatever the next object you are expecting it to point. So I did try sizeof(void) and got result 1. We need to understand that incrementing a type pointer where type is other than void doesn't equal to incrementing a void pointer. Size of each object must be used to calculate the offset from base of the array pointed by void pointer.
        Coming to heapsort, it is better explained in CLRS book. I implemented it as it is. No heuristics added. It is available here. I documented the source code clearly. Be careful. Don't get stuck like me.

No comments:

Post a Comment