C Program to implement HEAP sort


Levels of difficulty: / perform operation:

Data structures using C, Heap sort algorithm starts by building a heap from the given elements,and then heap removes its largest element from the end of partially sorted array. After removing the largest element, it reconstructs the heap, removes the largest remaining item, and places it in the next open position from the end of the partially sorted array. This is repeated until there are no items left in the heap and the sorted array is full. Elementary implementations require two arrays – one to hold the heap and the other to hold the sorted elements.

C Program

#include<stdio.h>
void heapsort(int[],int);
void heapify(int[],int);
void adjust(int[],int);
main() {
	int n,i,a[50];
	system("clear");
	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("\t%d",a[i]);
	printf("\n");
}
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;
		adjust(a,i);
	}
}
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;
	}
}
void adjust(int a[],int n) {
	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;
}





Quantitative Aptitude
Reasoning
Programming
Interview