Hey,
I'm in a class in which the assignment here is to sort integers. We were called on to use two different sorting methods: InsertSort and HeapSort. My InsertSort works just fine. My HeapSort, however, does not; when the HeapSort() function is finished, the integers are still out of order.
My instructor is having us use a slightly different approach to the usual HeapSort algorithm (although the "heapify," or in my case, "Adjust()" function is the same). I'm only trying to sort 10 integers for now, and while the sorted array is "closer," it's still not correct. Here's what happens with the output (i had it print the array each step it took. Also, I had it add a line break in between building the max heap and the actual sort process)
9, 4, 5, 8, 2, 1, 6, 3, 7,
9, 4, 5, 8, 2, 1, 6, 3, 7,
9, 4, 6, 8, 2, 1, 5, 3, 7,
9, 4, 6, 8, 2, 1, 5, 3, 7,
9, 8, 6, 7, 2, 1, 5, 3, 4,
9, 8, 6, 7, 2, 1, 5, 3, 4,
9, 8, 6, 7, 2, 1, 5, 3, 4,
9, 8, 6, 7, 2, 1, 5, 3, 4,
4, 8, 6, 7, 2, 1, 5, 3, 9,
3, 8, 6, 7, 2, 1, 5, 4, 9,
5, 8, 6, 7, 2, 1, 3, 4, 9,
8, 7, 6, 1, 2, 5, 3, 4, 9,
8, 7, 6, 1, 2, 5, 3, 4, 9,
8, 7, 6, 1, 2, 5, 3, 4, 9,
2, 7, 6, 1, 8, 5, 3, 4, 9,
7, 1, 6, 2, 8, 5, 3, 4, 9,
7, 1, 6, 2, 8, 5, 3, 4, 9,
6, 1, 7, 2, 8, 5, 3, 4, 9,
1, 6, 7, 2, 8, 5, 3, 4, 9,
1, 6, 7, 2, 8, 5, 3, 4, 9,My instructor has told me that the algorithm and my functions are "exactly right," but I think my issue is somewhere where I'm actually calling the Adjust() function from HeapSort(). I know that the mistake I made here is probably really stupid, but still, all help would be greatly appreciated.
I know there are probably other issues with my code. All I need help with at the moment are the HeapSort() and Adjust() functions. What am I doing wrong?
main.cpp:
#include <iostream>
#include <fstream>
#include "Sorts.h"
using namespace std;
void main()
{
int input; //where the input numbers are stored before they're passed to the class
char command; //where the input command char is stored
Sorts toSort; //the sorting class
ifstream infile; //the input file variable, reads in from the text file where the ints are
infile.open("passig05data.txt");
ofstream echofile; //the outputreport.txt file goes here
echofile.open("outputreport.txt", ios::app);
cout<<"Welcome to CSCI 203 Program 5.\n";
echofile<<"Welcome to CSCI 203 Program 5.\n";
cout<<"Now reading input file...";
echofile<<"Now reading input file...";
while (infile>>input)
toSort.Insert(input);
cout<<"done.\n";
echofile<<"done.\n";
infile.close();
cout<<toSort.getEntries()<<" values were read in.\n\n";
cout<<"Command? >> ";
echofile<<"Command? >> ";
cin>>command;
while (command != 'q') //if 'q' is entered, the program quits
{
if (command == 'i') //if 'i' is entered, call InsertSort()
{
echofile<<"i"<<endl;
toSort.InsertSort();
}
if (command == 'h') // if 'h' is entered, HeapSort()
{
echofile<<"h"<<endl;
toSort.HeapSort();
}
cout<<"Command? >> ";
echofile<<"Command? >> ";
cin>>command;
}
echofile<<"q"<<endl;
cout<<"So long, and farewell.\n";
echofile<<"So long, and farewell.\n";
}We are called to use a class header and implementation file where all the sort functions are. Here's Sorts.cpp:
//------------------------------------------------------------------------------------
// Sorts.cpp
//
// This is the CLASS IMPLEMENTATION FILE for the Sorts class.
//
// Preconditions: None.
//
// Postconditions: None.
//
//------------------------------------------------------------------------------------
#include <iostream>
#include <fstream>
#include <time.h>
#include <string>
#include <sstream>
#include "Sorts.h"
using namespace std;
//------------------------------------------------------------------------------------
// Sorts(Void)
//
// This is the CTOR. It resets all class variables to 0 and all arrays to 0.
//
// Preconditions: None.
//
// Postconditions: None.
//
//------------------------------------------------------------------------------------
Sorts::Sorts(void)
{
index=0;
int i;
for (i=0; i<MAX; i++)
{
values[i]=0;
is[i]=0;
heap[i]=0;
}
}
//------------------------------------------------------------------------------------
// getTime()
//
// Takes an amount of seconds, and converts that value to a readable string.
//
// Preconditions: A "seconds" value must be passed to the function.
//
// Postconditions: When finished, it will return a string with text that shows how
// many minutes and seconds were in the amopunt of seconds passed to the function.
//
//------------------------------------------------------------------------------------
string Sorts::getTime(int sec)
{
string strmin=" minute(s), ";
string strsec=" second(s)";
int minutes=0;
string out;
stringstream m;
stringstream s;
minutes = sec/60;
sec = sec%60;
m<<minutes;
s<<sec;
out.append(m.str());
out.append(strmin);
out.append(s.str());
out.append(strsec);
return out;
}
//------------------------------------------------------------------------------------
// insert()
//
// Takes an integer and adds it to the array of values.
//
// Preconditions: An integer value must be passed to this function.
//
// Postconditions: When finished, the value will be added to the newest index in the
// array, and the index integer value will be raised by 1.
//
//------------------------------------------------------------------------------------
void Sorts::Insert(int input)
{
values[index]=input;
index++;
//cout<<input<<" was inserted, the index is now "<<index<<endl;
}
//------------------------------------------------------------------------------------
// InsertSort()
//
// Copies the values to a temporary array and then sorts it.
//
// Preconditions: None.
//
// Postconditions: Copies the values to a temporary array and performs InsertSort
// on it. Captures the time before and after the sort, calls getTime() to return
// the exact number of seconds it took to sort.
//
//------------------------------------------------------------------------------------
void Sorts::InsertSort()
{
ofstream outfile;
outfile.open("InsertSorted.txt");
ofstream echofile;
echofile.open("outputreport.txt", ios::app);
//copy the input array to a temorary one for now.
char time1[9], time2[9];
for (int i=0; i<MAX; i++)
is[i]=values[i];
time_t start, end;
double difference;
time(&start);
_strtime(time1);
for (int j = 2; j < index; j++)
{
for (int k = 0; k < j; k++)
{
if (is[j] < is[k])
{
int temp = is[k];
is[k] = is[j];
is[j] = temp;
}
}
}
time(&end);
_strtime(time2);
difference = difftime(end,start);
outfile<<"Number Sorted: "<<index<<endl;
outfile<<"Start Time: "<<time1<<endl;
outfile<<"End Time: "<<time2<<endl;
outfile<<"Time Elapsed: "<<getTime(difference)<<endl;
cout<<endl<<"It took "<<getTime(difference)<<" to InsertSort "<<index<<" values.\n";
echofile<<endl<<"\nIt took "<<getTime(difference)<<" to InsertSort "<<index<<" values.\n";
for (int i=0; i<index; i++)
{
for (int j=0; j<10; j++) //keeping it ten ints per line
{
outfile<<is[i]<<" ";
i++;
}
outfile<<endl;
}
}
void Sorts::printArray()
{
cout<<"The array is:\n";
for (int i=0; i<index; i++)
{
cout<<is[i]<<", ";
}
cout<<endl;
}
int Sorts::getEntries()
{
return index;
}
//------------------------------------------------------------------------------------
// HeapSort()
//
// Performs HeapSort on the list of values.
//
// Preconditions: None.
//
// Postconditions: Like with InsertSort(), it copies the numbers to a temporary
// array, creates the max heap first by calling Adjust(), then sorts the numbers.
// It captures the time before we start the sort, and the time when the sort is
// finished, then writes the integers to an oputput file.
//
//------------------------------------------------------------------------------------
void Sorts::HeapSort()
{
int i=0, j=0;
ofstream outfile;
outfile.open("HeapSorted.txt");
heap[0]=0;
//copy the input array to a temorary one for now.
for (int i=1; i<=(index+1); i++) //starts at 1 because a heap has nothing at the zero index
heap[i]=values[i-1];
printHeap();
time_t start, end;
double difference;
time(&start);
_strtime(time1);
for (i=index/2; i>0; i--) //this loop and function here, as i was told by the instructor, eliminates the need for
Adjust(heap, i, index); //a "buildmaxheap" function.
cout<<endl;
for (j=index-1; j>0; j--)
{
swap(heap[1], heap[j+1]);
Adjust(heap, heap[1], j);
}
printHeap();
time(&end);
_strtime(time2);
difference = difftime(end,start);
outfile<<"Number Sorted: "<<index<<endl;
outfile<<"Start Time: "<<time1<<endl;
outfile<<"End Time: "<<time2<<endl;
outfile<<"Time Elapsed: "<<getTime(difference)<<endl;
cout<<endl<<"It took "<<getTime(difference)<<" to HeapSort "<<index<<" values.\n";
echofile<<endl<<"\nIt took "<<getTime(difference)<<" to HeapSort "<<index<<" values.\n";
for (int i=1; i<=index; i++)
{
for (int j=0; j<10; j++) //keeping it ten ints per line
{
outfile<<is[i]<<" ";
i++;
}
outfile<<endl;
}
}
void Sorts::printHeap()
{
//cout<<"The heap is:\n";
for (int i=1; i<=index; i++)
{
cout<<heap[i]<<", ";
}
cout<<endl;
}
//------------------------------------------------------------------------------------
// Adjust(Void)
//
// Heapifies the heap.
//
// Preconditions: This function must be passed the actual array to be manipulated,
// the "position" integer, as well as the "number of values" integer.
//
// Postconditions: When finished, the current tree will become a heap.
//
//------------------------------------------------------------------------------------
void Sorts::Adjust(int list[], int i, int n) //also called "heapify"
{
int lchild, rchild, larger;
larger = lchild = (2*i);
if (lchild <= n) //if the root is not a leaf...
{
rchild = lchild+1;
//if the root has a child, then find the larger child
if ((rchild <= n) && (list[rchild] > list[lchild]))
larger = rchild;
//if root value is smaller than the left child, swap.
if (list[i] < list[larger])
{
swap(list[i], list[larger]);
Adjust(list, larger, n);
}
}
printHeap(); //for now, i have it print the heap at each step so i know exactly what the sort is doing
}Sorts.h:
class Sorts {
public:
static const int MAX = 100;
Sorts(void);
void Insert(int input);
void InsertSort();
void HeapSort();
void Adjust(int list[], int i, int n);
void printArray();
void printHeap();
std::string getTime(int sec);
int getEntries();
int index;
private:
int values[MAX];
int is[MAX];
int heap[MAX];
};And here is the input data we're supposed to use. passig05data.txt: 9 4 5 8 2 1 6 3 7
