C Program for Heap Sort Algorithm

Heap Sort:

         The Heap Sort Algorithm is an improved version  of the selection sort. The heap sort selects an element from the unsorted portion of the list, but it is the largest element. Because heap is a tree structure. A Heap is tree structure in which the root contains the largest element in the tree.

Program:

#include<stdio.h>
#include<conio.h>
void arrange(int *, int);
void hs(int *, int, int);
int main()
{
             int a[20],i,j,n,tmp,k;
             clrscr( );
             printf("\nEnter Number of elements:");
             scanf("%d",&n);
             printf("\nEnter %d of elements:",i);
            for(i=0; i<n; i++)
            {
                   scanf("%d",&a[i]);
                   arrange(a,i);
            }
            j=n;
            for(i=0; i<j; i++)
           {
                   tmp=a[0];
                  a[0]=a[n];
                  a[n]=tmp;
                  n--;
                  hs(a,0,n);
           }
           printf("\nSorting list in ascending order:");
           n=j;
           for(i=0; i<n; i++)
          {
               printf("\n%d ",a[i]);
          }
           getch( );
}
void arrange(int *a, int i)
{
          int tmp;
          tmp=a[i];
          while((i>0)&&(a[i/2]<tmp))
         {
                  a[i]=a[i/2];
                  i=i/2;
          }
          a[i]=tmp;
}
void hs(int *a, int i, int n)
{
          int tmp,j;
          tmp=a[i];
          j=i*2;
          while(j<=n)
         {
               if((j<n)&&(a[j]<a[j+1]))
               {
                        j++;
               }
               if(a[j]<a[j/2])
               {
                       break;
               }
               a[j/2]=a[j];
               j=j*2;
          }
          a[j/2]=tmp;
}

Output:

Enter Number of elements:5

Enter 5 of elements:4
1
20
5
9

Sorting list in ascending order:
1
4
5
9
20