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

Latest

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

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

No comments:

Post a Comment