Heap sort

Heapsort is a comparison-based sorting algorithm to create a sorted array (or list), and is part of the selection sort family.
Although somewhat slower in practice on most machines than a well-implemented quicksort, it has the advantage of a more favorable worst-case O(n log n) runtime.

Algorithm

MAX-HEAPIFY(A,i)

1. l = LEFT(i)

2. r = RIGHT(i)

3. if l <= A.heap-size and A[l] > A[i]

4. 		largest = l

5. else largest = i

6. if r <= A.heap-size and A[r] > A[largest]

7. 		largest = r

8. if largest != i

9. 		exchange A[i] with A[largest]

10.		MAX-HEAPIFY(A,largest)



BUILD-MAX-HEAP(A)

1. A.heap-size = A.length

2. for i = [A.length/2] downto 1

3. 		MAX-HEAPIFY(A, i)



HEAPSORT(A)

1. BUILD-MAX-HEAP(A)

2. for i = A.length downto 2

3. 		exchange A[1] with A[i]

4. 		A.heap-size = A.heap-size - 1

5. 		MAX-HEAPIFY(A, 1)

Heap sort Implementation

#include<stdio.h>

#include<conio.h>

void manage(int *, int);

void heapsort(int *, int, int);

void main()

{

	int arr[20];

	int i,j,size,tmp,k;

	clrscr();

	printf("\n\t\t\t------- Heap sorting method -------\n\n");

	printf("Enter the number of elements to sort : ");

	scanf("%d",&size);

	printf("Enter The Element In Array\n");

	for(i=1; i<=size; 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\t\t------- Heap sorted elements -------\n\n");

	size=j;

	printf("Sorted Elements:\t");

	for(i=1; i<=size; i++)

	printf("%d\t ",arr[i]);

	getch();

}

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