27 Aug Heap Sort in C
Let us see how to implement Heap Sort in C Language.
What is Heap Sort?
Heap Sort is based on the binary heap data structure. In this, we find the maximum element and place it in the end. Then this is repeated for all the elements.
Given example explains the steps required in sorting.
The array before sorting starts is:
|
1 2 3 |
9 1 5 8 2 |
Now, this is built into a binary max heap using heapify. The resultant heap represented as an array is:
|
1 2 3 |
9 8 5 1 2 |
Now, one by one the root element of the max heap is extracted and put at the end. Then heapify is called to convert the remaining elements into a heap again. This is represented as follows:
|
1 2 3 |
8 2 5 1 9 |
|
1 2 3 |
5 2 1 8 9 |
|
1 2 3 |
2 1 5 8 9 |
|
1 2 3 |
1 2 5 8 9 |
Hence the final sorted array is obtained which is:
|
1 2 3 |
1 2 5 8 9 |
Source Code
The source code for Heap Sort is as follows:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
#include < stdio.h > void heapify(int arr[], int n, int i) { int temp; int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l < n && arr[l] > arr[largest]) largest = l; if (r < n && arr[r] > arr[largest]) largest = r; if (largest != i) { temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp; heapify(arr, n, largest); } } void heapSort(int arr[], int n) { int temp; for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); for (int i = n - 1; i >= 0; i--) { temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; heapify(arr, i, 0); } } int main() { int arr[] = { 9, 1, 5, 8, 2 }; int n = 5; int i; printf("Given array is: \n"); for (i = 0; i < n; i++) printf("%d ", arr[i]); printf("\n"); heapSort(arr, n); printf("\nSorted array is: \n"); for (i = 0; i < n; ++i) printf("%d ", arr[i]); } |
Output
The output obtained for the above code is:
No Comments