Program to implement Heap sort

Objective: C program to sort the elements using Heap sort in divide and conquer technique

Concept: A max (min) heap is complete binary tree with the property that the value at each node is at least as large as (as small as) the values at its children (if they exist) Call this property the heap property.

Algorithm:
Step 1: Start

Step 2: Declare the variables.

Step 3: Enter the 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 arrays elements.

Step 6: Combine the two sorted arrays.

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

Step 8: Stop

				
#include<stdio.h>
void heapsort(int[],int);
void heapify(int[],int);
void main()
{
int n,i,a[50];
clrscr();
printf("\nEnter the limit:");
scanf("%d",&n);
printf("\nEnter the elements:");
for (i=0;i<n;i++)
scanf("%d",&a[i]);
heapsort(a,n);
printf("\nThe Sorted Elements Are:\n");
for (i=0;i<n;i++)
printf("\n %d",a[i]);
printf("\n");
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;
}
}
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;
}
}
{
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;
}