Heap sort not functioning properly.

[TLaCoil]

I have a heap sort function with cstring keys for an assignment. It seems to work with some sets of data but not others, and I'm not sure why. Below are the functions involved. Any help would be appreciated.

void StockHeap::sortRecords()
{//Sorts with heap sort algorithm.
	int unsorted = 0, newcopy = 0;

	makeHeap();

	unsorted = size;

	while(unsorted > 1) 
	{
		unsorted--; //Adjusts the partition on the unsorted data.
		stockSwap(stocks[0], stocks[unsorted]); //Puts the largest in unsorted into sorted part of array.
		reheapDown(unsorted); //Calls reheapification with appropriate index.
	}
}

void StockHeap::reheapDown(int index)
{//Moves nodes into appropriate position from top down.
	int i = 0;
	bool down = true;
	
	while(i < index && down)
	{
		if(2*i+2 < index)
		{//Has 2 children.
			if(strcmp(stocks[2*i+1].getTag(), stocks[2*i+2].getTag()) >0)
			{//If left child first alphabetically.
				if(strcmp(stocks[i].getTag(), stocks[2*i+1].getTag()) <0)
				{
					stockSwap(stocks[i], stocks[2*i+1]);
					i = 2*i+1;
				}
				else
					down = false;
			}
			
			else
			{//Right child first alphabetically.
				if(strcmp(stocks[i].getTag(), stocks[2*i+2].getTag()) <0)
				{
					stockSwap(stocks[i], stocks[2*i+2]);
					i = 2*i+1;
				}
				else
					down = false;				
			}
		}

		else if(2*i+1 < index)
		{//Has 1 child.
			if(strcmp(stocks[i].getTag(), stocks[2*i+1].getTag()) <0)
			{
				stockSwap(stocks[i], stocks[2*i+1]);
				i = 2*i+1;
			}
			else
				down = false;
		}
		
		else //No children.
			down = false;
	}		
}

void StockHeap::makeHeap()
{//Builds a complete heap for records.
	for(int i = size-1; i > 0; i--) 
		reheapUp(i);
cout << endl;
printRecords(cout);
}

void StockHeap::reheapUp(int index)
{//Moves nodes into appropriate position upwards.
	int i = index-1;

	while(i > 0 && strcmp(stocks[i].getTag(), stocks[(i-1)/2].getTag()) > 0) 
	{
		stockSwap(stocks[i], stocks[(i-1)/2]);
		i = (i-1)/2;
	}
}

[Duthomhas]

Your makeHeap()/reheapUp() algorithm is incorrect. reheapUp() should not be finding parents.

There should be one function that applies the heap property to node i and i's descendants only. You can fix reheapDown() to do this properly:

void StockHeap::reheapDown( int i, int index )

Then makeHeap() only needs use the correct function:

void StockHeap::makeHeap()
{
    for (int i = size-1;  i > 0;  i--)
        reheapDown(i,size);
}

A couple of other notes:

(1)
You have tended to using very odd names for things. Try to find something less generic for some of your names.

For example, 'index' is less useful than 'one_past_end' or 'heap_size' or 'first_sorted_index':

void StockHeap::pushDown( int node_index, int heap_size )

In the sortRecords() function you have named this very value "unsorted", which is good in that context.

(2)
Avoid flaggy code.
Everywhere you have down = false could be replaced with a simple break (or return!).

(3)
The commentary on lines 27 and 38 is incorrect. The larger is the last alphabetically.

(4)
Look at the relationship between lines 3 and 7.

(5)
I do not know whether your assignment requires this or not, but it is a significant design flaw to bind your data as an appendage to a sorting algorithm.

Your data should exist without reference to any specific sorting algorithm, and, if necessary, supply some method to sort it.

In other words, your data is:

    heap_sorted_data_list
      + stuff to maintain data
      + stuff to sort data

When it should be:

    data_list
      + stuff to maintain data
      + possibly including a member method to sort it (and/or maintain it's sorted state)

Don't worry about changing it now; follow your assignment. Just be aware that binding data to a sort algorithm is a mistake. Apply algorithms to your data. (Don't apply data to your algorithms.)

Overall, a good start. If you wish to see a visual representation of the heap property, check out the FAQ:
http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/heapsort/#heap-property

Hope this helps.