Program For Heap Sort
Below is the implementation of the above method:
C
// C Program for HeapSort #include <stdio.h> // Heapify function void heapify( int arr[], int n, int i) { int temp, maximum, left_index, right_index; // currently assuming i postion to // be holding the largest value maximum = i; // right child index right_index = 2 * i + 2; // left child index left_index = 2 * i + 1; // if left index value is grater than the current index // value if (left_index < n && arr[left_index] > arr[maximum]) maximum = left_index; // if right index value is grater than the current index // value if (right_index < n && arr[right_index] > arr[maximum]) maximum = right_index; // checking if we needed swaping the elements or not if (maximum != i) { temp = arr[i]; arr[i] = arr[maximum]; arr[maximum] = temp; heapify(arr, n, maximum); } } // HeapSorting function void heapsort( int arr[], int n) { int i, temp; // performing heapify on the non leaf nodes so n/2 - 1 // to 0 are the non leaf nodes for (i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } // the current array is changed to max heap for (i = n - 1; i > 0; i--) { temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; heapify(arr, i, 0); } } // Driver code int main() { // initializing the array int arr[] = { 20, 18, 5, 15, 3, 2 }; int n = 6; // Displaying original array printf ( "Original Array : " ); for ( int i = 0; i < n; i++) { printf ( "%d " , arr[i]); } printf ( "\n" ); heapsort(arr, n); // Displaying sorted array printf ( "Array after performing heap sort: " ); for ( int i = 0; i < n; i++) { printf ( "%d " , arr[i]); } return 0; } |
Original Array : 20 18 5 15 3 2 Array after performing heap sort: 2 3 5 15 18 20
Complexity of the Above Method:
Time complexity: O(n*log n), where ‘n’ is number of elements in the array.
Auxiliary Space: O(1)
C Program for Heap Sort
Heap sort is a comparison-based sorting technique. It works on the data structure known as “the binary heap”. It is one of the most efficient sorting algorithms. It takes relatively less time than selection sort, bubble sort, and insertion sort. Heap sort is an unstable sorting algorithm since the position of a similar element gets changed. Heap sort works with Max Heap (Heap is a complete binary tree. A max heap has a parent node greater than the child nodes).
In this article, we going to deep dive into the sorting algorithm and working of heap sort. We are also going to implement heap sort in C language.
Contact Us