Sort the elements of an array A in ascending order.

Heapsort algorithm inserts all elements into a heap, then removes them from the root of a heap until the heap is empty.

Sort can be done in place with the array to be sorted.
Instead of deleting an element,
exchange the first element (maximum) with the last element and reduce the heap size (array size).
Then, heapify the first element.
Continue this process until the number of remaining elements is one.

#include<stdio.h>
#include<conio.h>
#define SIZE 50
void main()
{
	int A[SIZE], N;
	int i, j;
	int left, right ,max, aux;

	do {
		printf("Enter the dimension: ");
		scanf("%d", &N);
	} while (N <= 0 || N > SIZE);

	for (i = 0; i < N; i++)
	{
		printf("Enter A[%d]: ", i);
		scanf("%d", &A[i]);
	}

 	// Heap sort
	// step 1: modify the array to be a max-heap
	// for each non leaf mode, percolate down
	for(j=(N-1)/2; j>=0; j--)
	{
		// percolate down j	
		i=j;
		while(1)
		{
			left=2*i+1;
			if(left<N && A[left] > A[i])
				max=left;
			else
				max=i;
			right=2*i+2;
			if(right<N && A[right] > A[max])
				max=right;
		 
			if(max!=i)
			{
				aux=A[i];
				A[i]=A[max];
				A[max]=aux;
				i=max; // percolate down from i
			}
			else
				break;
		
		}
	}

	// step 2: get the max, exchange it with the last element of 
	// the non sorted array, and percolate down the root
	for(j=N-1;j>=0;j--)
	{
		aux=A[j];
		A[j]=A[0];
		A[0]=aux;
		
		//percolate down element 0, which is the max element in the non sorted array
		i=0;
		while(1)
		{
			left=2*i+1;
			if(left<j && A[left] > A[i]) // attention: we check till index j not N
				max=left;
			else
				max=i;
			right=2*i+2;
			if(right<j && A[right] > A[max])
				max=right;
		 
			if(max!=i)
			{
				aux=A[i];
				A[i]=A[max];
				A[max]=aux;
				i=max; // percolate down from i
			}
			else
				break;
		
		}

	}


	printf("\n\n** After sorting ** \n");
	for (i = 0; i < N; i++)
	{
		printf("A[%d]=%d\n", i, A[i]);
	}

	getch();
}