C program for Heap Sort.

heap-sort.c

C program to sort the elements of the array in ascending order using Heap Sort technique is as follows:

#include<stdio.h>
#include<conio.h>

#define SIZE 6
int array_to_sort[SIZE];

void build_heap();
void heap_sort();
void swap(int *num_1, int *num_2);

void main()
{
	int i;

	clrscr();

	//Get the elements of Array
	for(i=1; i<SIZE; i++)
	{
		printf("\nEnter element %d: ",i);
		scanf("%d", &array_to_sort[i]);
	}

	//Print the unsorted array.
	printf("\n\nUnsorted elements of Array are: ");
	for(i=1; i<SIZE; i++)
	{
		printf("%d ",array_to_sort[i]);
	}

	//Create heap tree
	build_heap();

	//Print the heap array.
	printf("\n\nUnsorted elements of Heap Array are: ");
	for(i=1; i<SIZE; i++)
	{
		printf("%d ",array_to_sort[i]);
	}

	heap_sort();

	//Print the sorted array.
	printf("\n\nSorted elements of Array are: ");
	for(i=1; i<SIZE; i++)
	{
		printf("%d ",array_to_sort[i]);
	}

	getch();
}

void build_heap()
{
	int i, j, parent;
	int temp_array[SIZE];

	for(i=1; i<SIZE; i++)
	{
		temp_array[i] = array_to_sort[i];

		j = i;
		while(j > 1)
		{
			parent = (int) (j/2);

			if(temp_array[parent] < temp_array[j])
			{
				swap(&temp_array[j], &temp_array[parent]);

				j = parent;
			}
			else
			{
				break;
			}
		}
	}

	for(i=1; i<SIZE; i++)
	{
		array_to_sort[i] = temp_array[i];
	}
}

void heap_sort()
{
	int i, j, lchild, rchild;

	for(i=SIZE-1; i>1; i--)
	{
		swap(&array_to_sort[1], &array_to_sort[i]);

		j = 1;
		while(j < i-1)
		{
			lchild = 2*j;
			rchild = 2*j+1;

			if((lchild < i) && (rchild < i))
			{
				if((array_to_sort[j] < array_to_sort[lchild]) && (array_to_sort[lchild] > array_to_sort[rchild]))
				{
					swap(&array_to_sort[j], &array_to_sort[lchild]);
					j = lchild;
				}
				else if((array_to_sort[j] < array_to_sort[rchild]) && (array_to_sort[rchild] > array_to_sort[lchild]))
				{
					swap(&array_to_sort[j], &array_to_sort[rchild]);
					j = rchild;
				}
				else
				{
					break;
				}
			}
			else if(lchild < i)
			{
				if((array_to_sort[j] < array_to_sort[lchild]))
				{
					swap(&array_to_sort[j], &array_to_sort[lchild]);
					j = lchild;
				}
				else
				{
					break;
				}
			}
			else if(rchild < i)
			{
				if((array_to_sort[j] < array_to_sort[rchild]))
				{
					swap(&array_to_sort[j], &array_to_sort[rchild]);
					j = rchild;
				}
				else
				{
					break;
				}
			}
			else
			{
				break;
			}
		}
	}
}

void swap(int *num_1, int *num_2)
{
	int temp;
	temp = *num_1;
	*num_1 = *num_2;
	*num_2 = temp;
}