C Online Compiler
Example: Heap Sort using Recursion in C
C
C++
C#
Java
Python
PHP
main.c
STDIN
Run
// Heap Sort using Recursion #include <stdio.h> // Function to maintain the heap property in a subtree rooted at index i. // n is the size of the heap. void heapify(int arr[], int n, int i) { // Step 1: Initialize 'largest' as the root of the current subtree int largest = i; // Calculate indices of left and right children int left = 2 * i + 1; // Left child index int right = 2 * i + 2; // Right child index // Step 2: Check if the left child exists and is greater than the current largest if (left < n && arr[left] > arr[largest]) { largest = left; } // Step 3: Check if the right child exists and is greater than the current largest if (right < n && arr[right] > arr[largest]) { largest = right; } // Step 4: If the largest element is not the current root, swap them // and recursively heapify the affected subtree. if (largest != i) { int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp; // Recursively call heapify on the subtree that was affected by the swap heapify(arr, n, largest); } } // Main function to perform heap sort on an array of size n void heapSort(int arr[], int n) { // Step 1: Build a max-heap (rearrange the array) // We start from the last non-leaf node (n/2 - 1) and go up to the root (0). // This ensures that when heapify is called on a node, its children are already heaps. for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } // Step 2: Extract elements one by one from the heap // After building the heap, the largest element is at arr[0]. // We swap it with the last element, reduce the heap size, and re-heapify. for (int i = n - 1; i > 0; i--) { // Move the current root (largest element) to the end of the array int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // Call heapify on the reduced heap (excluding the last element which is now sorted) // to maintain the max-heap property for the remaining elements. heapify(arr, i, 0); } } // Utility function to print an array void printArray(int arr[], int n) { for (int i = 0; i < n; ++i) { printf("%d ", arr[i]); } printf("\n"); } int main() { // Step 1: Define an example array to be sorted int arr[] = {12, 11, 13, 5, 6, 7}; int n = sizeof(arr) / sizeof(arr[0]); printf("Original array: "); printArray(arr, n); // Step 2: Perform heap sort using the defined function heapSort(arr, n); printf("Sorted array: "); printArray(arr, n); return 0; }
Output
Clear
ADVERTISEMENTS