I am trying to understand what is going wrong with my heap sort. It compiles, populates the vector, prints it and gets to this one particular method call and I can't seem to track the issue for the life of me. I implemented Wikipedias psudo-code to try to get it to work but I just can't figure it out. Hopefully you all can help me spot why its taking x>10 minutes and still not finishing. Its probably looping somewhere...
void
heapSort(vector <int>& sortablevector, size_t count)
{
make_vector_heap(sortablevector, count);
size_t end = count-1; //in languages with zero-based arrays the children are 2*i+1 and 2*i+2
while ( end > 0 )
{
//(swap the root(maximum value) of the heap with the last element of the heap)
swap( sortablevector[end], sortablevector[0] );
//(decrease the size of the heap by one so that the previous max value will
//stay in its proper placement)
end = end - 1;
//(put the heap back in max-heap order)
downHeap( sortablevector, 0, end );
}
}
// My version of wikipedia's 'Heapify' method
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
void
make_vector_heap(vector <int>& sortablevector, size_t count)
{
size_t start = ( count - 1) / 2;
while ( start >= 0 )
{
//(sift down the node at index start to the proper place such that all nodes below
//the start index are in heap order)
downHeap(sortablevector, start, count-1 );
start = start - 1;
}
}
By far the quickest & easiest way to solve run time problems is to use a debugger. Should be easy if you are using an IDE. Step through the code 1 line at a time, keep an eye on the value of your variables to deduce where it all goes wrong.
Found this code with a google search ( heap sort C++ example )- don't know how good it is. Some of the others returned by google weren't very goodIMO.