CODEWITHSUNDEEP
c++algorithmsortingheapsort
user2411290
user2411290

Reputation: 641

C++: HeapSort function outputting wrong numbers

I'm relatively new to C++/Algorithms, and I'm not quite sure what's wrong with my heapSort function. Given the numbers (6, 2, 9, 1, 5), I am outputting the following incorrect numbers:

9
4197040
2
4196422
6

Thanks for looking.

#include <iostream>

using namespace std;

void heapSort(int arr [], int size);
void reheapDown(int arr[], int root, int bottom);
void swap(int & num1, int & num2);

int main()
{
   int arr[5] = {6, 2, 9, 1, 5};

   heapSort(arr, 5);

   for (int i = 0; i < 5; i++)
   cout << arr[i] << endl;

   return 0;
}

void heapSort(int arr [], int size){

    int i;

    for (i = size/2 -1; i >= 0; i--)
    reheapDown(arr, i, size-1);

    for (i = size - 1; i >= 1; i--){
    swap(arr[0], arr[i]);
    reheapDown(arr, 0, i-1);

    }

}

void reheapDown(int arr[], int root, int bottom){

    int max, right, left;

    left = root * 2 + 1;
    right = root * 2 + 2;

    if (left <= bottom)

        max = left;

    else{
        if (arr[left] <= right)
        max = right;
        else
        max = left;
    }
    if (arr[root] < arr[max]){

        swap(arr[root], arr[max]);
        reheapDown(arr, max, bottom);
    }
}

void swap(int & num1, int & num2){

    int temp;

    temp = num1;
    num1 = num2;
    num2 = temp;

}

Upvotes: 0

Views: 92

Answers (1)

Brock Hargreaves
Brock Hargreaves

Reputation: 872

At least one problem is that you are accessing out of bounds:

void reheapDown(int arr[], int root, int bottom){

    int max = 0;

    int left = root * 2 + 1;
    int right = root * 2 + 2;


    if (left <= bottom)
        max = left;
    else{
        if (left < 0){
            throw std::runtime_error("Uh oh, left is less than zero");
        }
        if (left > 4){
            throw std::runtime_error("Uh oh, left is greater than 4");
        }

        if (arr[left] <= right)
            max = right;
        else
        max = left;
    }
    if (arr[root] < arr[max]){
        if (root < 0){
            throw std::runtime_error("Uh oh, root is less than zero");
        }
        if (root > 4){
            throw std::runtime_error("Uh oh, root is greater than 4");
        }
        if (root < 0 || root > 4){
            throw std::runtime_error("Uh oh");
        }
        swap(arr[root], arr[max]);
        reheapDown(arr, max, bottom);
    }
}

Will output:

terminate called after throwing an instance of 'std::runtime_error'
  what():  Uh oh, left is greater than 4

Upvotes: 1

Related Questions