Scribd
Upload
13 views2 pages

Program 4 HeapSort

The document provides a C program that implements heapsort to sort a list of student IDs. It includes functions for sorting and maintaining the heap property, as well as measuring the time taken and memory usage during execution. The time complexity of heapsort is O(n log n) and the space complexity is O(1).

Uploaded by

geetha sree
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
13 views2 pages

Program 4 HeapSort

The document provides a C program that implements heapsort to sort a list of student IDs. It includes functions for sorting and maintaining the heap property, as well as measuring the time taken and memory usage during execution. The time complexity of heapsort is O(n log n) and the space complexity is O(1).

Uploaded by

geetha sree
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

4) Suppose you are given a list of students who are assigned IDs.

Write a program to sort these


students based on their id’s using heapsort. Find its time and space complexity
#include <stdio.h>
#include <sys/time.h>
#include <sys/resource.h>

// Function declarations
void heapSort(int a[], int n);
void siftDown(int a[], int root, int bottom);

int main() {
int a[100], n, i;
struct timeval tv1, tv2;
struct rusage r_usage;

printf("Enter the number of elements (max 100):\n");


scanf("%d", &n);

if (n > 100 || n < 1) {


printf("Invalid number of elements. Must be between 1 and 100.\n");
return 1;6t
}

printf("Enter the elements:\n");


for (i = 0; i < n; i++) {
scanf("%d", &a[i]);
}

gettimeofday(&tv1, NULL);
heapSort(a, n);
gettimeofday(&tv2, NULL);

printf("Sorted elements are:\n");


for (i = 0; i < n; i++) {
printf("%d ", a[i]);
}
printf("\n");

double elapsedTime = (tv2.tv_sec - tv1.tv_sec) * 1e6 + (tv2.tv_usec - tv1.tv_usec);


printf("Time taken by Heap Sort: %.2f microseconds\n", elapsedTime);

getrusage(RUSAGE_SELF, &r_usage);
printf("Memory usage: %ld kilobytes\n", r_usage.ru_maxrss);a

return 0;
}

// Heap sort function


void heapSort(int a[], int n) {
int i, temp;

// Build max heap


for (i = n / 2 - 1; i >= 0; i--)
siftDown(a, i, n - 1);
// Heap sort
for (i = n - 1; i >0; i--) {
temp = a[0];
a[0] = a[i];
a[i] = temp;
siftDown(a, 0, i - 1);
}
}

// Function to maintain heap property


void siftDown(int a[], int root, int bottom) {
int done = 0, maxChild, temp;

while ((root * 2 + 1 <= bottom) && (!done)) {


int leftChild = root * 2 + 1;
int rightChild = root * 2 + 2;

if (rightChild <= bottom && a[rightChild] > a[leftChild])


maxChild = rightChild;
else
maxChild = leftChild;

if (a[root] < a[maxChild]) {


temp = a[root];
a[root] = a[maxChild];
a[maxChild] = temp;
root = maxChild;
} else {
done = 1;
}
}

You might also like