Problem with Heap Sort

[codergem]

The following code is for heap sort but its not working properly.
According to my analysis the Logic is correct but still its not showing
the correct output.
Thanks.

#include "stdafx.h"
#include<iostream>
#include<stdlib.h>

using namespace std;

int n=10,s[10]={11,2,9,13,57,25,17,1,90,3},heapsize;

void swap(int a,int b)
{
int temp=s;
s=s[a];
s[a]=temp;
}

void keepheap(int i)
{
int l,r,p,q,t,largest,m;

l = 2*i;
r = 2*i + 1;

p = s[l];
q = s[r];
t = s;

if(l<=heapsize && p > t)
largest = l;
else
largest = i;

m = s[largest];

if(r<=heapsize && q > m)
largest = r;

if(largest != i)
{
swap(i, largest);
keepheap(largest);
}
}


void makeheap(int n)
{
heapsize=n;
for(int i=(n/2)-1; i>=1; i--)
keepheap(i);
}

void heapsort()
{
makeheap(n);

for(int i=n; i>=2; i--)
{
swap(1,i);
heapsize--;
keepheap(i);
}
}

 

[Alan Johnson]

The following code is for heap sort but its not working properly.
According to my analysis the Logic is correct but still its not showing
the correct output.
Thanks.

A general observation before I go into specific errors. Arrays in C++
start at index 0, not at index 1. That is, if you define an array:
int s[10];

the values you may access are s[0] through s[9]. Specificalloy, s[10]
is NOT a valid value.

#include "stdafx.h"
#include<iostream>
#include<stdlib.h>

You don't need any of these headers for any of the code you posted.

using namespace std;

int n=10,s[10]={11,2,9,13,57,25,17,1,90,3},heapsize;

Avoid global variables (not an error, just a guideline).

void swap(int a,int b)
{
int temp=s;
s=s[a];
s[a]=temp;
}

There is nothing wrong with your swap function, but in general try to

void keepheap(int i)
{
int l,r,p,q,t,largest,m;

First problem, you should check to make sure i is valid before
continuing. Something like:
if (i >= heapsize)
return;

l = 2*i;
r = 2*i + 1;

If you use a zero based array to represent a tree, the left subchild
will be at 2*i+1, and the right at 2*i+2. So change this to:
l = 2*i+1;
r = 2*i+2;

p = s[l];
q = s[r];
t = s;

What if l or r are outside of the valid range? You don't check for that
until later. I suggest dropping these variables completely, as they
just serve to muddy up your algorithm.

if(l<=heapsize && p > t)
largest = l;
else
largest = i;

Again. s[heapsize] is NOT valid. So you should be checking for (l <
heapsize). Also, having removed p,q, and t, the second clause should be
(s[l] > s). Putting it all together:

if (l < heapsize && s[l] > s)
largest = l;
else
largest = i;

This is probably a case where I'd use the ternary operator, and collapse
this whole thing to:

largest = (l < heapsize && s[l] > s) > l : i;

If that confuses you, ignore it, as the if statement will do just as well.

m = s[largest];

Again, drop this variable. It just makes the algorithm harder to follow.

if(r<=heapsize && q > m)
largest = r;

This suffers from the same problem. You should be checking for (r <
heapsize && s[r] > s[largest]). You could also use the ternary operator
here if it looks cleaner to you.

if(largest != i)
{
swap(i, largest);
keepheap(largest);
}
}


void makeheap(int n)
{
heapsize=n;
for(int i=(n/2)-1; i>=1; i--)
keepheap(i);
}

Same issue. Arrays are zero based. You should loop while (i >= 0).

void heapsort()
{
makeheap(n);

for(int i=n; i>=2; i--)

Arrays are zero based. As your intent here was to skip the last
iteration of the loop (which is fine) you should loop while (i >= 1).
Likewise, s[n] is NOT valid. You should start with i=n-1.

{
swap(1,i);

Arrays are zero based (last time, I promise). You want to swap(0, i).

heapsize--;
keepheap(i);

Here you are trying to maintain the heap property on the element you
just removed from the heap, which doesn't make any sense. The element
for which you (possibly) destroyed the heap property is the root, so
keepheap(0).

}
}

Good luck.