Sunday, December 12, 2010

Heap Sort

//Program to Perform Heap Sort
#include
#include

#define SIZE 10
class heap
{
int a[SIZE],n;

public:
heap()
{
n=0;
}
void read();
void swap(int*,int*);
void heapsort();
void display();
};
void heap::read()
{
cout<<" HEAP SORT\n";
cout<<" ---------\n\n";
cout<<"\nEnter the number of elements:";
cin>>n;

cout<<"\nEnter the "<
for(int i=0;i< n;++i)
cin>>a[i];

heapsort();
}

void heap::swap(int *x,int *y)
{
int temp;
temp=*x;
*x=*y;
*y=temp;
}

void heap::heapsort()
{
int i,s,f;
for(i=1;i {
s=i;
f=(s-1)/2;
while(a[f] {
swap(&a[f],&a[s]);
s=f;
if(s==0)
break;
f=(s-1)/2;
}
}
for(i=n-1;i>=1;--i)
{
swap(&a[0],&a[i]);
f=0;
s=1;
if(i==1)
break;
if(i>2)
if(a[2]>a[1])
s=2;
while(a[f] {
swap(&a[f],&a[s]);
f=s;
s=2*f+1;
if(i>s+1)
if(a[s+1]>a[s])
s=s+1;
if (s>=i)
break;
}
}
}

void heap::display()
{
cout<<"\nThe Sorted List is\n\n";
for(int i=0;i cout<<" "< }
void main()
{
clrscr();
heap h;
h.read();
h.display();
getch();
}



OUTPUT



HEAP SORT
---------

Enter the number of elements:7

Enter the 7 elements:
89
4
1
78
103
8
11

The Sorted List is

1 4 8 11 78 89 103

No comments:

Post a Comment