my task is to write the code to a heapsort according to pseudo code. It should heapsort the input Array (4 3 2 5 6 7 8 9 12 1) and then print it with the printHeap method. I know for a fact that the printHeap works, because I have already used it with a method called buildHeap (to build max heap binary trees, but you all already know that :)) and there it works flawlessly, so my problem lies in heapSort.
It sorts correctly and prints it in the way it's supposed to (parent -- child 1, parent -- 2, etc.), only issue is, that the biggest and last value, which is 12, suddenly turns into 24 and I have no clue why.
The code is the following:
void heapSort(int a[], int n){
int x = n+1;
int i;
int temp;
buildMaxHeap(a, n);
for (i = n; i >= 1; i--){
temp = a[i];
a[i] = a [0];
a [0] = temp;
x--;
heapify(a, 0, x);
}
void printHeap(int a[], int n){
int i;
printf("graph g { \n");
for (i = 0; i < n/2; i++){
printf("%d -- %d\n", a[i], a[left(i)]);
if (right(i) < n){
printf("%d -- %d\n", a[i], a[right(i)]);
}
}
printf("}\n");
Output is following:
1 2 3 4 5 6 7 8 9 24
graph g {
1 -- 2
1 -- 3
2 -- 4
2 -- 5
3 -- 6
3 -- 7
4 -- 8
4 -- 9
5 -- 24
}
just so you know what exactly I have done, I will attach the while .c file here: https://onedrive.live.com/redir?resid=8BC629F201D2BC63!26268&authkey=!AFqVlm9AptiZ_xM&ithint=file%2cc
Really grateful for your help!
Cheers Arik
Well, you observe an undefined behavior. (I personally on an online IDE got 0 instead of the 12(24).)
Try:
void heapSort(int a[], int n)
{
int x = n; /* changed from n+1 */
int i;
int temp;
buildMaxHeap(a, n);
for (i = n-1; i >= 0; i--){ /*<-- changed*/
temp = a[i];
a[i] = a[0];
a[0] = temp;
x--;
heapify(a, 0, x);
}
}
Your arrays in almost all general purpose languages of today start with index 0[For thorough information see wiki.] You loop your array for (i = n; i >= 1; i--) wrongly and since the heap is max, don't process the first element and go out of bounds with the last. Although arithmetic with the nth element is defined in the standard, it is not meant so rather < n and some pointer work.
On a side note, you can use macros (#defines) for the left, right etc. functions to improve performance and ease the reading.
I hope that saves the day and the AlgoDat Exercise.