/*C Program to implement heapsort and insertion sort*/
#include<stdio.h>
#include<conio.h>
#include<process.h>
void insertion(int a[],int n)
{
  int i,k,y;
  for(k=1;k<n;k++)
  {
    y=a[k];
    for(i=k-1;i>=0&&a[i]>y;i--)
    a[i+1]=a[i];
    a[i]=y;
  }
  for(i=0;i<n;i++)
  printf("%d ", a[i]);
}

void heapsort(int k[],int n)
{
  int q,tmp,i,j,key;
  for(q=n;q>=2;--q)
  {
    tmp=k[1]; k[i]=k[q]; k[q]=tmp;
    i=1;
    key=k[i];
    j=2;
    if((j+1)<q)  if(k[j+1]>k[j])  j++;
    while((j<=(q-1))&&(k[j]>key))
    {
      k[i]=k[j];
      i=j; j=2*i;
      if((j+1)<q)  if(k[j+1]>k[j])  j++;
      else if(j>n) j=n;
      k[i]=key;
    } /*end of while*/
  } /*end of for*/
  for(i=1;i<=n;i++)  printf("%d", k[i]);
} /*end of function*/

void main()
{
  int n,i,a[50],p;
  clrscr();
  printf("How many elements? ");
  scanf("%d", &n);
  printf("Enter the elements:\n");
  for(i=1;i<=n;i++)
  scanf("%d", &a[i]);
  printf("\n1.Heap Sort      2.Insertion Sort\n");
  printf("Your Choice?  ");
  scanf("%d", &p);
  if(p==1) { heapsort(a,n); exit(0); }
  if(p==2) { insertion(a,n); exit(0); }
  else printf("Sorry ! Facility not available.");
  getch();
}