C++

Forum

 
Not sure what's wrong with my HeapSort Code

leo255 (139)
Hi guys,

I don't get what I did wrong here. For some reason, I'm getting some floating point numbers in my output (shown below), and it's not sorting at all. I am trying my best to figure out the problems in the code.

9
4197040
2
4196422
6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
 
#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;

}
leo255 (139)
Getting a little bit closer...

I added:

1
2
 
if (left == bottom)
			max = left;


I now don't have any floating point numbers...My output is now:

1
2
9
5
6


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
 
#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);
void output(int arr[], int size);

int main()
{
   int arr[5] = {6, 2, 9, 1, 5};
   
   heapSort(arr, 5);
   output(arr, 5);
   
   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){
        
        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;
    
}

void output(int arr[], int size){
    
    cout << "HeapSort \n\n";
    
    for (int i = 0; i < size; i++)
   cout << arr[i] << endl;
   
}
Last edited on
Duthomhas (13206)
You are mixing indices and values.

It might be helpful to go through your reheapDown() function and make note of whether each instance of a variable should be comparing (or using) an index or a value in the array.

For example, you have declared the indices 'left' and 'right'. On line 48, you compare a value in the array (arr[left]) with an index (right).

Hope this helps.

[edit] Shameless plug for further reading:
http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/heapsort/
Last edited on
Topic archived. No new replies allowed.