DAA - 4.Heapsort lab program (BCA-IV sem KSWU)

 

 Program 4 . Program to Sort N Numbers using Heapsort

Algorithm:

Step 1: Start the process.

Step 2: Declare the variables.

Step 3: Enter the list of elements to be sorted using the get function.

Step 4: Divide the array list into two halves the lower array list and upper array list

using the merge sort function.

Step 5: Sort the two array list.

Step 6: Combine the two sorted arrays.

Step 7: Display the sorted elements using the get() function.

Step 8: Stop the process

SOURCE CODE :

/*Heap sort */

#include<stdio.h>

#include<time.h>

void heapsort(int[],int);

void heapify(int[],int);

void adjust(int[],int);

void main()

{

     int n,i,a[50];

     clock_t start,end;

       double ctu;

     clrscr();

     start=clock();

     printf("\n Enter the limit: ");

     scanf("%d",&n);

     printf("\n Enter the elements: ");

     for(i=0;i<n;i++)

       scanf("%d",&a[i]);

     heapsort(a,n);

     printf("\n The sorted elements are :\n");

     for(i=0;i<n;i++)

     printf("\n %d",a[i]);

     printf("\n");

     end= clock();

     ctu=((double)(end-start))/CLOCKS_PER_SEC;

     printf("The elapsed time is %f sec ",ctu);

     getch();

}

void heapsort(int a[],int n)

{

    int i,t;

    heapify(a,n);

    for(i=n-1;i>0;i--)

    {

       t=a[0];

       a[0]=a[i];

       a[i]=t;

       adjust(a,i);

    }

}

void heapify(int a[],int n)

{

   int k,i,j,item;

   for(k=1;k<n;k++)

   {

     item=a[k];

     i=k;

     j=(i-1)/2;

     while((i>0)&&(item>a[j]))

     {

       a[i]=a[j];

       i=j;

       j=(i-1)/2;

     }

     a[i]=item;

   }

}

void adjust(int a[],int n)

{

  int i,j,item;

  j=0;

  item=a[j];

  i=2*j+1;

  while(i<=n-1)

  {

    if(i+1<=n-1)

      if(a[i]<a[i+1])

      i++;

      if(item<a[i])

      {

a[j]=a[i];

j=i;

i=2*j+1;

      }

      else

      break;

  }

  a[j]=item;

}

OUTPUT :