Sherd Sherd - 1 month ago 15
C++ Question

Heap Sort from Intro to Algorithms in C++ Implementation using Vectors

I have been working on Heap Sort Functions in C++ that follows the logic from our class book, Intro to Algorithms 3rd edition and am not getting the desired output. Have been working through this in my head and am close, but I am not seeing my error. I am using vectors and have omitted the code that reads the values from a separate text file.

Any ideas on where I am going wrong with the indexes in each version? Adding, the input list I am using to test is 10 15 8 3 16 20 11 12 5 7 4 1 19 13 2 6 9 14 17 18.

The first method I tried is closer to the book but was giving output of 10 19 20 15 17 16 11 12 13 9 18 14 8 7 6 4 3 2 5 1. This is my preferred solution if I could figure out how I am messing up the indexing.

void maxHeapify(vector<int>&);
void buildMaxHeap(vector<int>&);
void heapSort(vector<int>&);

int main(int argc, char * argv[])
{
if (argc <= 1)
{
std::cerr << "A file was not found or is not accessable." << std::endl;
return (1);
}

vector<int> list;
int loc;

ifstream fin(argv[1]);

while (fin >> loc)
{
list.push_back(loc);
}

// print unsorted list
cout << "Unsorted List:\n";
for (int i = 0; i < list.size(); ++i)
cout << list[i] << ' ';
cout << endl;

heapSort(list);

// print sorted list
cout << "Sorted List:\n";
for (int i = 0; i < list.size(); ++i) {
cout << list[i] << " ";
}
cout << endl;

cin.get();

return(0);
}

/* Heap Sort from Textbook using Vectors ***********************************/
void maxHeapify(vector<int>& A, int i)
{
int largest;
int l = 2 * i;
int r = (2 * i) + 1;

if ((l <= A.size()) && (A[l] > A[i]))
largest = l;
else
largest = i;

if ((r <= int(A.size())) && (A[r] > A[largest]))
largest = r;

if (largest != i)
{
swap(A[i], A[largest]);
maxHeapify(A, largest);
}
}

void buildMaxHeap(vector<int>& A)
{
for (int i = int((A.size()-1) / 2); i >= 1; i--)
{
maxHeapify(A, i);
}
}

void heapSort(vector<int>& A)
{

buildMaxHeap(A);
for (int i = int(A.size()-1); i >= 2; i--)
swap(A[1], A[i]);
maxHeapify(A, 1);
}
}


The second method I tried ends up with an output 2 1 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19 20 to 50 on a randomly sorted list of 50 integers but is correct on a list of only 20 random integers. The code is as follows:

void maxHeapify(vector<int>&, int, int);
void buildMaxHeap(vector<int>&, int);
void heapSort(vector<int>&, int);

int main(int argc, char * argv[])
{
if (argc <= 1)
{
std::cerr << "A file was not found or is not accessable." << std::endl;
return (1);
}

vector<int> list;
int loc;

ifstream fin(argv[1]);

while (fin >> loc)
{
list.push_back(loc);
}

// print unsorted list
cout << "Unsorted List:\n";
for (int i = 0; i < list.size(); ++i)
cout << list[i] << ' ';
cout << endl;

clock_t begin = clock();

heapSort(list, int(list.size() - 1));

clock_t end = clock();
double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC; //only reports in seconds, need to replace.

printf("Heap Sort Elasped time is %0.6f seconds.", elapsed_secs);
cout << endl;

// print sorted list
cout << "Sorted List:\n";
for (int i = 0; i < list.size(); ++i) {
cout << list[i] << " ";
}
cout << endl;

cin.get();

return(0);
}

/* Heap Sort from Textbook using Vectors ***********************************/
void maxHeapify(vector<int>& A, int i, int n)
{
int largest;
int l = 2 * i;
int r = (2 * i) + 1;

if ((l <= n) && (A[l - 1] > A[i - 1]))
largest = l;
else
largest = i;

if ((r <= n) && (A[r - 1] > A[largest - 1]))
largest = r;

if (largest != i)
{
swap(A[i - 1], A[largest - 1]);
maxHeapify(A, largest, n);
}
}

void buildMaxHeap(vector<int>& A, int n)
{
for (int i = n / 2; i >= 1; i--)
{
maxHeapify(A, i, n);
}
}

void heapSort(vector<int>& A, int n)
{

buildMaxHeap(A, n);
for (int i = n; i >= 2; i--)
{
swap(A[0], A[i]);
maxHeapify(A, 1, i - 1);
}
}

Answer

I ended up figuring out the indexing issues. I still couldn't get the first method to work due to the fact that I was using pointers to point at A and the size was never correct. So I stuck with my second method. Here is the corrected code.

void maxHeapify(vector<int>&, int, int);
void buildMaxHeap(vector<int>&, int);
void heapSort(vector<int>&, int);

int main(int argc, char * argv[])
{
if (argc <= 1)
{
    std::cerr << "A file was not found or is not accessable." << std::endl;
    return (1);
}

vector<int> list;
int loc;

ifstream fin(argv[1]);

while (fin >> loc)
{
    list.push_back(loc);
}

// print unsorted list
//cout << "Unsorted List:\n";
//for (int i = 0; i < list.size(); i++)
//  cout << list[i] << ' ';
//cout << endl;

clock_t begin = clock();

heapSort(list, int(list.size() - 1));

clock_t end = clock();
double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;  //only reports in seconds, need to replace.  

printf("Heap Sort Elasped time is %0.6f seconds.", elapsed_secs);
cout << endl;

// print sorted list
//cout << "Sorted List:\n";
//for (int i = 0; i < list.size(); i++) {
//  cout << list[i] << " ";
//}
//cout << endl;

cin.get();

return(0);
}

/* Heap Sort from Textbook using Vectors ***********************************/
void maxHeapify(vector<int>& A, int i, int n)
{
int largest;
int l = 2 * i;
int r = (2 * i) + 1;

if ((l <= n) && (A[l - 1] > A[i - 1]))
    largest = l;
else
    largest = i;

if ((r <= n) && (A[r - 1] > A[largest - 1]))
    largest = r;

if (largest != i)
{
    swap(A[i - 1], A[largest - 1]);
    maxHeapify(A, largest, n);
}
}

void buildMaxHeap(vector<int>& A, int n)
{
for (int i = n / 2; i >= 1; i--)
{
    maxHeapify(A, i, n);
}
}

void heapSort(vector<int>& A, int n)
{

buildMaxHeap(A, n);
for (int i = n; i >= 1; i--) // Remove last element from heap
{
    swap(A[0], A[i]);
    maxHeapify(A, 1, i); // Heapify reduced heap
}
}