PROGRAM 9: HEAPSORT WITH TIME CALCULATION
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 1000
int count = 0;
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
// If left child is larger than root
if (left < n && arr[left] > arr[largest])
largest = left;
// If right child is larger than largest so far
if (right < n && arr[right] > arr[largest])
largest = right;
// If largest is not root
if (largest != i)
{
count++; // Increment operation count
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
// Recursively heapify the affected subtree
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n)
{
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
for (int i = n - 1; i >= 0; i--)
{
// Move current root to end
count++; // Increment operation count
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// Call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
int main()
{
int a[SIZE], x[SIZE], y[SIZE], z[SIZE];
int n, i, j, c1, c2, c3;
clock_t start, end;
double time_taken;
printf("\nEnter the size of the array :");
scanf("%d", &n);
// Input array
printf("\nRead the elements: ");
for (i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
// Time calculation for heap sort
start = clock();
heapSort(a, n);
end = clock();
time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("\nSorted array : ");
for (i = 0; i < n; i++)
{
printf("%d\t", a[i]);
}
printf("\n");
printf("\nTime taken for heap sort: %f seconds\n", time_taken);
printf("\nCount = %d\n", count);
// Complexity test for ascending, descending, and random cases
printf("\nSize\tASC\tDESC\tRAND\n");
for (i = 16; i < SIZE; i *= 2)
{
for (j = 0; j < i; j++)
{
x[j] = j; // Ascending
y[j] = i - j - 1; // Descending
z[j] = rand() % i; // Random
}
// Ascending case
count = 0;
start = clock();
heapSort(x, i);
end = clock();
c1 = count;
// Descending case
count = 0;
start = clock();
heapSort(y, i);
end = clock();
c2 = count;
// Random case
count = 0;
start = clock();
heapSort(z, i);
end = clock();
c3 = count;
printf("%d\t%d\t%d\t%d\n", i, c1, c2, c3);
}
return 0;
}
