My heapsort is not functioning the way it should, and I was wondering if perhaps one of you could help point me in the right direction. Much thanks in advance should you care to look! :)

If it helps anyone, I posted it on pastebin.org with syntax highlighting: http://www.pastebin.org/55997

Source code:

/******************************************************************************
* Program:
*	Assignment 17, Heapsort Program
* Summary: 
*	From the command line, reads in a file containing numbers, placing the
*	numbers in a vector. The program performs a heap sort (a O(n log n)
*	sort) on the vector, and prints out the values.
******************************************************************************/
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

///////////////////////////////////////////////////////////////////////////////
// main
///////////////////////////////////////////////////////////////////////////////

/**** Prototypes used in main *****/
vector < int > buildVector(string filename);
void heapify(vector < int > &tree, int wall);
void percolateDown(vector < int > &tree, int pos, int wall);
void heapsort(vector < int > &myVector);
void display (const vector < int > &myVector);

/******************************************************************************
* main
* Desc:
*	From the command line, reads in a file containing numbers, placing the
*	numbers in a vector. The program performs a heap sort (a O(n log n)
*	sort) on the vector, and prints out the values.
******************************************************************************/
int main(int argc, char* argv[])
{
   string filename;
   //Check for proper usage and invalid input
   if (argc <= 1 || argc > 2)
   {
	  cout << "Usage: <executable> <file with numbers to be sorted>\n";
	  exit(1);
   }
   else //input is good
   {
	  filename = argv[argc - 1];
   }

   vector < int > numbers = buildVector(filename); //build the number vector

   cout << "Before:\n";
   display(numbers);

   heapsort(numbers);

   cout << "After:\n";
   display(numbers);

   return 0;
}

/******************************************************************************
* buildVector
* Desc: Reads in a file with numbers, stores them in a vector, and returns
*	   the vector of numbers.
* Input: string filename containing the numbers
* Return: vector myVector containing the numbers
******************************************************************************/
vector < int > buildVector(string filename)
{
   ifstream inStream;
   vector < int > myVector;

   //open file and check for success
   inStream.open(filename.c_str());
   if (inStream.fail()) //file failed to open
   {
	  cout << "Unable to open file \"" << filename
		   << "\" in function buildVector()\n";
	  exit(1);
   }
   else //successfully opened file
   {
	  int number; //numbers read in from file
	  //push on all numbers from file onto vector
	  while (inStream >> number)
	  {
		 myVector.push_back(number);
	  }
	  inStream.close();
   }
   return myVector;
}

/******************************************************************************
* heapify
* Desc: Transforms a complete binary tree into a heap (root is largest value).
* Input: integer vector tree to heapify, int wall
******************************************************************************/
void heapify(vector < int > &tree, int wall)
{
   int start = (wall - 2) / 2;
   while (start >= 0)
   {
	  percolateDown(tree, start, wall - 1);
	  --start;
   }
}

/******************************************************************************
* percolateDown
* Desc: "Percolates" smaller values down to the bottom of the tree, creating
*	   a maxheap.
* Input: integer vector tree, int root (where we begin), int wall
******************************************************************************/
void percolateDown(vector < int > &tree, int root, int wall)
{
   int child;
   while ((2 * root + 1) <= wall)
   {
	  child = 2 * root + 1;
	  if (child + 1 <= wall && tree[child] < tree[child + 1])
	  {
		 ++child;
	  }
	  if (tree[root] < tree[child])
	  {
		 int temp = tree[root];
		 tree[root] = tree[child];
		 tree[child] = temp;
		 root = child;
	  }
	  else
	  {
		 break;
	  }
   }
}

/******************************************************************************
* display
* Desc: Displays the contents of a vector.
* Input: Vector to be displayed
******************************************************************************/
void display (const vector < int > &myVector)
{
   for (int i = 0; i < myVector.size(); ++i)
   {
	  cout << myVector[i];
	  if (i + 1 < myVector.size())
	  {
		 cout << ' ';
	  }
   }
   cout << endl;
}

/******************************************************************************
* heapsort
* Desc: Performs a heapsort on a given vector, with O(n log n).
* Input: Vector to be sorted
******************************************************************************/
void heapsort(vector < int > &myVector)
{
   heapify(myVector, myVector.size());
   int wall = myVector.size() - 1;
   int temp; //used for swapping values
   while (wall > 0)
   {
	  temp = myVector[wall];
	  myVector[wall] = myVector[0];
	  myVector[0] = temp;
	  percolateDown(myVector, 0, wall);
	  --wall;
   }
}

Input and expected/actual output:

Test 1:

Input:
45 22 35 21 9 40 31 39 3 39 23 29 16 49 16 22 20 7 35 7 31 47 1 12 10 41 14 15 13 31 42 8 3 26 28 11 15 9 49 18 47 22 46 12 20 11 33 40 18 18 47 48 15 47 10 24 38 23 39 1 4 30 8 6 5 36 16 20 44 15 38 40 36 33 2 6 44 35 46 11 3 42 9 18 39 19 41 27 41 30 27 44 10 35 49 15 20 15 35 13

Expected:
1 1 2 3 3 3 4 5 6 6 7 7 8 8 9 9 9 10 10 10 11 11 11 12 12 13 13 14 15 15 15 15 15 15 16 16 16 18 18 18 18 19 20 20 20 20 21 22 22 22 23 23 24 26 27 27 28 29 30 30 31 31 31 33 33 35 35 35 35 35 36 36 38 38 39 39 39 39 40 40 40 41 41 41 42 42 44 44 44 45 46 46 47 47 47 47 48 49 49 49

Actual:
7 2 1 9 23 5 3 1 8 6 8 9 3 10 10 11 7 11 11 12 12 15 13 13 14 15 15 9 15 6 15 15 31 16 16 16 4 18 18 18 19 20 20 20 20 21 22 22 22 23 10 24 26 27 27 28 29 30 30 31 31 3 33 33 35 49 35 35 35 35 36 36 38 38 39 39 39 39 40 40 40 41 41 41 42 42 44 44 44 45 46 46 47 47 47 47 48 49 18 49

Test 2:

Input:
35 26 10 1 17 21 47 13 5 10 26 20 41 12 39 37 41 49 9 23 25 24 27 30 18 37 17 40 37 35 47 21 10 7 21 27 27 18 39 31 27 15 50 18 26 38 5 16 37 13 39 11 37 16 41 4 2 7 44 38 42 40 9 1 46 30 28 22 47 17 3 24 31 2 41 7 40 45 23 26 8 11 36 45 27 26 48 28 33 41 15 24 31 23 25 26 2 2 48 49

Expected:
1 1 2 2 2 2 3 4 5 5 7 7 7 8 9 9 10 10 10 11 11 12 13 13 15 15 16 16 17 17 17 18 18 18 20 21 21 21 22 23 23 23 24 24 24 25 25 26 26 26 26 26 26 27 27 27 27 27 28 28 30 30 31 31 31 33 35 35 36 37 37 37 37 37 38 38 39 39 39 40 40 40 41 41 41 41 41 42 44 45 45 46 47 47 47 48 48 49 49 50

Actual:
10 2 2 5 7 4 2 1 7 5 2 7 9 9 10 3 10 11 11 12 13 13 17 15 15 16 21 16 17 8 17 18 18 18 20 21 21 1 22 23 23 23 24 24 25 25 26 26 26 26 26 26 27 27 27 27 27 28 28 30 30 46 31 31 31 33 35 35 36 37 37 37 37 37 38 38 39 39 39 40 40 40 41 41 41 41 41 42 44 45 45 24 47 47 47 48 48 49 49 50

Your percolateDown function should have <, not <= in both the while question and the if question。。。。

void percolateDown(vector < int > &tree, int root, int wall)
{
   int child;
   
   while ((2 * root + 1) < wall)
   {
      child = 2 * root + 1;
	  if (child + 1 < wall && tree[child] < tree[child + 1])
	  {
		 ++child;
	  }
	  if (tree[root] < tree[child])
	  {
		 int temp = tree[root];
		 tree[root] = tree[child];
		 tree[child] = temp;
		 root = child;
	  }
	  else
	  {
		 break;
	  }
   }
}
commented: Awesome! Thanks for finding that mistake, it was so tiny! :P +0

Awesome! It works perfectly now. Thanks for helping me find that mistake, it was so tiny that I was going nuts trying to figure out what was wrong. :)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.