Heap Sort

Sorting Algorithm

Share

In this tutorial we will be learning about Heap sort algorithm. In this sorting algorithm we first build a heap using the given elements. If we want to sort the elements in ascending order we create a
 Min Heap. And to sort the elements in descending order we create a 
Max Heap.Once the heap is created we delete the root node from the heap and put the last node in the root position and repeat the steps till we have covered all the elements.

C Code

In this example we are sorting the elements in ascending order. We are saving element from index 1. So, index 0 is set to -1.

#include <stdio.h>

void display(int arr[], int size);
void heapSort(int arr[], int size);
void minHeap(int arr[], int size);

int main() {
	//unsorted elements
	//we are saving elements from index 1
	//so, index 0 is set to -1
	int arr[] = {-1, 40,60,10,20,50,30};

	//size of the array
	int n = sizeof(arr)/sizeof(arr[0]);

	//output unsorted elements
	display(arr, n);

	//sort the elements
	heapSort(arr, n);

	//display sorted elements
	display(arr, n);

	return 0;
}

void display(int arr[], int size) {
	int i;
	for(i = 0; i < size; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
}

void heapSort(int arr[], int size) {
	//variables
	int i, j, tmp, sorted[size];
	sorted[0] = -1;	//index 0 is not used so set to -1

	//sort
	for(i = size , j = 1; i >= 1; i--, j++) {
		minHeap(arr, i);
		sorted[j] = arr[1];
		arr[1] = arr[i - 1];	//put last element to root node
	}

	//set the result
	for(i = 0; i < size; i++) {
		arr[i] = sorted[i];
	}
}

void minHeap(int arr[], int size) {
	int i, left, right, tmp, val;

	for(i = size / 2; i >= 1; i--) {

		//taking 1 as the start index
		//if parent node = i
		//so left child = 2i
		//and right child = 2i+1
		tmp = i;
		left = (2 * i);
		right = (2 * i) + 1;

		if(left < size && arr[left] < arr[tmp]) {
			tmp = left;
		}

		if(right < size && arr[right] < arr[tmp]) {
			tmp = right;
		}

		if(tmp != i) {
			val = arr[i];
			arr[i] = arr[tmp];
			arr[tmp] = val;
			minHeap(arr, size);
		}
	}
}
Share

Recently Added