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

Question

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);
}
}

This is too broad with no minimal reproducible example. Did you debug it? — Khalil Khalaf
– Khalil Khalaf, Commented Oct 21, 2016 at 4:14
Yes, the debugger doesn't catch anything as there isn't technically anything wrong. I know it is an indexing issue. I run in on a random list of 20 characters to verify the sort is correct, test it again on a list of 100, and finally run it on the final list of 10,000. I have added the input list which is coming from a text file where each line is a new integer. — Sherd
– Sherd, Commented Oct 21, 2016 at 14:34

Sumeet · Accepted Answer · 2016-10-21 04:31:42Z

The algorithm provided in the book considers the indices as 1,2,3....N, they start from 1.

So just follow the algorithm but keep one thing in mind when we access array we must subtract 1 from the index

So your first method code should be:

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);
}
}

In second method, what you are doing wrong is that you are checking bounds with respect to 0 based index.

We cannot go by 0 based index here, because for 0 index, the left child is at index 1, but 2*0 is 0 only, So the only way is to use 1 based index everywhere and only while accessing elements you subtract - 1

Sherd · Accepted Answer · 2016-10-25 00:07:31Z

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
}
}

Collectives™ on Stack Overflow

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

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related