Sort the given list of numbers using Heap Sort MC9217 DATA STRUCTURES LAB Anna University lab manual download - Computer Programming

# Computer Programming

C C++ Java Python Perl Programs Examples with Output -useful for Schools & College Students

## Saturday, January 29, 2011

Sort the given list of numbers using Heap Sort MC9217 DATA STRUCTURES LAB Anna University lab manual download

Aim: To write a program to sort the given list of numbers using heap sort.

Algorithm:

1. Start
2. Read the value of n
3. check while(n>=2) then item =delete heap(a,n)
a[n]=item, n--
1. Insert heap(assigning int var) while (i>1) && (item>a[par]) then
A[i]=a[par], i=par, par=i/2
1. Check if (par<1) then par=1
Delete heap (assign value)
1. Check while (right<=n) then if (Last ) = a[left]&&
[last]=a[right] then a[i]=last
1. Else if [a(left)]=a[right] then
A[i]=a[left], i=left; else a[i]=a[right]
1. Stop

Program Code
#include<stdio.h>
#include<math.h>
void heapsort(int x[],int n);
void main()
{
int a[100],n,i;
clrscr();
printf("\n\tHEAP SORT");
printf("\nEnter the number of elements:");
scanf("%d",&n);
printf("Enter the elements:\n");
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
heapsort(a,n);
printf("\n The sorted elements in the array are:");
for(i=1;i<=n;i++)
printf("\n%d",a[i]);
getch();
}
void cheap(int x[20],int n)
{
int s,f,key,q;
for(q=2;q<=n;++q)
{
s=q;
key=x[q];
f=(int)(s/2);
while((s>1)&&(key>x[f]))
{
x[s]=x[f];
s=f;
f=(int)(s/2);
if(f<1)
f=1;
}
x[s]=key;
}
}
void heapsort(int x[20],int n)
{
int i,temp,s,f,key;
cheap(x,n);
for(i=n;i>=2;--i)
{
temp=x[1];
x[1]=x[i];
x[i]=temp;
s=1;
key=x[s];
f=2;
if((f+1)<i)
if(x[f+1]>x[f])
f=f+1;
while((f<=(i-1))&&(x[f]>key))
{
x[s]=x[f];
s=f;
f=2*s;
if((f+1)<i)
if(x[f+1]>x[f])
f=f+1;
else
if(f>n)
f=n;
x[s]=key;
}
}
}