Heap Sorting method and algorithm

In heap sorting process:

First of all organizing the whole data to be sorted as a binary tree i.e. heap. And after that impletment heap sorting.

Step 1: (How to data organizing as binary tree?)

Remember only 2 rule:

Rule:1.

The parent node must be greater then child node.
If parent node is not greater then to child node not replace it with parent node. And if binary tree is large then, if relaceing child node(now its parent node) is greater then to great-parent node then its also is replace the great-parent node.

Rule:2.

New element always insert in left side and after right side of parent node.
If left side of parent element has already element then new element would be insert in right side. And if right side of parent node has already element then new element will be insert in left side.

Step 2: (How to perform heap sorting:)

Heap sorting

Q. Write a C program to sort 5 numbers using heap sorting method.


Ans.


/* c program for heap sorting method*/

#include<stdio.h>
#include<conio.h>
void manage(int *, int);
void heapsort(int *, int, int);
int main()
{
 int arr[20]; 
 int i,j,size,tmp,k;
 printf("\n\t------- Heap sorting method -------\n\n");
 printf("Enter the number of elements to sort : ");
 scanf("%d",&size);
 for(i=1; i<=size; i++)
 {
   printf("Enter %d element : ",i);
   scanf("%d",&arr[i]);
   manage(arr,i);
 }
 j=size;
 for(i=1; i<=j; i++)
 {
   tmp=arr[1];
   arr[1]=arr[size];
   arr[size]=tmp;
   size--;
   heapsort(arr,1,size);
 }
 printf("\n\t------- Heap sorted elements -------\n\n");
 size=j;
 for(i=1; i<=size; i++)
     printf("%d ",arr[i]);
 getch();
 return 0;
}


void manage(int *arr, int i)
{
 int tmp; 
 tmp=arr[i];
 while((i>1)&&(arr[i/2]<tmp))
 {
   arr[i]=arr[i/2];
   i=i/2;
 }
 arr[i]=tmp;
}


void heapsort(int *arr, int i, int size)
{
 int tmp,j;
 tmp=arr[i];
 j=i*2;
 while(j<=size)
 {
   if((j<size)&&(arr[j]<arr[j+1]))
      j++;
   if(arr[j]<arr[j/2]) 
      break;
   arr[j/2]=arr[j];
   j=j*2;
 }
 arr[j/2]=tmp;
}

/************* OUTPUT ***************/

Screen shot for Heap sorting C program

Related programs:

1. Heap sorting method and algorithm
2. Bubble sorting
3. Selection sorting
4. Insertion sorting
5. Insertion sorting using function
6. Shell sorting
7. Quick sorting
8. Merge sorting
9. Radix sorting
10. Liner sorting