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
