Heap Sort Algorithm in C
Steps of Heap Sort Algorithm
Write a program to sort n randomly generated elements using heapsort method. ( assignment 2, set B. SPPU)
- Build a Max Heap from the given elements.
- Repeat the following steps until the heap size becomes 1:
- Swap the root (maximum element) with the last node in the array.
- Reduce the heap size by one.
- Apply the heapify procedure to restore the heap property.
Dear students , before you implement this program it recommande to uderstant the heapsort concept and heapsort algorithm. Use following links to read and understant the concept.
Program in C
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// Function to swap elements
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Heapify function to maintain max heap property
void heapify(int arr[], int n, int i) {
int largest = i; // Initialize largest as root
int left = 2 * i + 1; // Left child
int right = 2 * i + 2; // Right child
// Check if left child is larger than root
if (left < n && arr[left] > arr[largest])
largest = left;
// Check if right child is larger than largest so far
if (right < n && arr[right] > arr[largest])
largest = right;
// If largest is not the root
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest); // Recursively heapify the affected subtree
}
}
// Function to perform Heap Sort
void heapSort(int arr[], int n) {
// Step 1: Build Max Heap
for (int i = n / 2 – 1; i >= 0; i–)
heapify(arr, n, i);
// Step 2: Extract elements one by one
for (int i = n – 1; i > 0; i–) {
swap(&arr[0], &arr[i]); // Move current root to end
heapify(arr, i, 0); // Heapify the reduced heap
}
}
// Function to print array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
printf(“%d “, arr[i]);
printf(“\n”);
}
// Main function
int main() {
int n;
printf(“Enter the number of elements: “);
scanf(“%d”, &n);
int arr[n];
// Random number generation
srand(time(0));
printf(“Randomly generated array: “);
for (int i = 0; i < n; i++) {
arr[i] = rand() % 100; // Generates numbers between 0-99
printf(“%d “, arr[i]);
}
printf(“\n”);
// Sorting the array using Heap Sort
heapSort(arr, n);
printf(“Sorted array: “);
printArray(arr, n);
return 0;
}
