What is the problem with this???

[codergem]

Helo friends
Could any of you please help me out with this problem.
To me this program of heap sort seems logically perfect but still the
output of this is not coming right,
I dont want to follow any other solution.Could any of you please take
out some precious time of yours in solving this big problem for me,
where m i going wrong???
Thanks in advance.


// heapsort111.cpp : Defines the entry point for the console
application.
//

#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>=0; i--)
keepheap(i);
}

void heapsort()
{
makeheap(n);

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


int _tmain(int argc, _TCHAR* argv[])
{
int i;
cout<<"The Initial Array is : ";
for(i=0;i<n;i++)
cout<<s<<"; ";

heapsort();

cout<<"\nTHe Sorted array is : ";
for(i=0;i<n;i++)
cout<<s<<"; ";

return 0;
}

 

[Jim Langston]

Helo friends
Could any of you please help me out with this problem.
To me this program of heap sort seems logically perfect but still the
output of this is not coming right,
I dont want to follow any other solution.Could any of you please take
out some precious time of yours in solving this big problem for me,
where m i going wrong???
Thanks in advance.


// heapsort111.cpp : Defines the entry point for the console
application.
//

#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>=0; i--)
keepheap(i);
}

void heapsort()
{
makeheap(n);

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


int _tmain(int argc, _TCHAR* argv[])
{
int i;
cout<<"The Initial Array is : ";
for(i=0;i<n;i++)
cout<<s<<"; ";

heapsort();

cout<<"\nTHe Sorted array is : ";
for(i=0;i<n;i++)
cout<<s<<"; ";

return 0;
}

Someone posts code and says "To me this program of heap sort seems logically
perfect but still the output of this is not coming right" I'll glance at the
code for obvious errors and go on may way.

If you want quick answers, show us what you expect the output to be, and
what the actual output is.

 

[Ian Collins]

int _tmain(int argc, _TCHAR* argv[])

What on Earth is this?

 

[Jim Langston]

int _tmain(int argc, _TCHAR* argv[])

What on Earth is this?

Microsoft junk.

He simply needs to not use precompiled headers.

 

[Howard]

Helo friends
Could any of you please help me out with this problem.
To me this program of heap sort seems logically perfect but still the
output of this is not coming right,

We don't know the "logic" of the program, since you haven't specified it in
comments anywhere.

Regarding the output: tell us what the output is, and what you expect it to
be, not just that it "is not coming right".

I dont want to follow any other solution.Could any of you please take
out some precious time of yours in solving this big problem for me,
where m i going wrong???
Thanks in advance.


// heapsort111.cpp : Defines the entry point for the console
application.
//

#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;

Why are you declaring n as a global variable here? Why not just pass 10 to
the function heapsort()? You're likely to have troubles (at least using
your debugger) with a local variable named n and a global variable also
named n. At the least, you might forget which one you're referring to at
any given time.

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

Comments as to what each function is supposed to do would really help here.
(And they should be part of your design process, before you actually add
code to the functions, not an afterthought.)

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

Ok, "largest" is a pretty good name, but the rest of those are meaningless,
and won't help you (or anyone else) figure out what they're used for.

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>=0; i--)
keepheap(i);
}

void heapsort()
{
makeheap(n);

You only call makeheap once, from here, and pass it the global variable n.
Why have a separate function makeheap at all? Why not just put the loop
from there in this function? I think that _might_ help you see what's going
on better in this case, (especially in relation to the variables n and
heapsize and the loops you're executing).

(I know it's good to break down code into single tasks, but you're not being
consistent when you put the first loop into makeheap, but keep the second
loop in this function.)

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


int _tmain(int argc, _TCHAR* argv[])

You should consider not using precompiled headers, removing the include of
stdafx.h above, and using a standard main function here.

{
int i;
cout<<"The Initial Array is : ";
for(i=0;i<n;i++)
cout<<s<<"; ";

heapsort();

cout<<"\nTHe Sorted array is : ";
for(i=0;i<n;i++)
cout<<s<<"; ";

return 0;
}

Use a debugger, and step through the code. See if it's doing what you
expect. Write down what you _expect_ to see at each step on paper, then
copmare against that. At some point, what you see in the debugger won't
match what you expected. That should point out the error in your code.

-Howard