This C program sorts a given array of integer numbers using Heap Sort technique.
Depending upon the value of MAX we create an integer array with numbers ranging from 0 to MAX – 1. Using random_shuffle function we randomize the array and the sort it using heap sort algorithm. Time Complexity of this algorithm is O( nlog(n) ).
Here is the source code of the C program to sort integers using Heap Sort technique. The C program is successfully compiled and run on a Linux system. The program output is also shown below.
/*
* C Program to sort an array using Heap Sort technique
*/
#include<stdio.h>
#include <stdlib.h>
#define MAX 25
void random_shuffle(int arr[])
{
int i, j, temp;
srand(time(NULL));
for (i = MAX - 1; i > 0; i--) {
j = rand()%(i + 1);
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
void max_heapify(int a[], int i, int heapsize)
{
int tmp, largest;
int l = (2 * i) + 1;
int r = (2 * i) + 2;
if ((l <= heapsize) && (a[l] > a[i]))
largest = l;
else
largest = i;
if ((r <= heapsize) && (a[r] > a[largest]))
largest = r ;
if (largest != i)
{
tmp = a[i];
a[i] = a[largest];
a[largest] = tmp;
max_heapify(a, largest, heapsize);
}
}
void build_max_heap(int a[], int heapsize)
{
int i;
for (i = heapsize/2; i >= 0; i--)
{
max_heapify(a, i, heapsize);
}
}
void heap_sort(int a[], int heapsize)
{
int i, tmp;
build_max_heap(a, heapsize);
for (i = heapsize; i > 0; i--)
{
tmp = a[i];
a[i] = a[0];
a[0] = tmp;
heapsize--;
max_heapify(a, 0, heapsize);
}
}
int main()
{
int i, r, heapsize;
int a[MAX];
for (i = 0; i < MAX; i++)
a[i] = i;
heapsize = MAX - 1;
random_shuffle(a);
printf("\n");
heap_sort(a, heapsize);
for (i = 0; i < MAX; i++)
printf("%d ", a[i]);
return 0;
}
$ gcc heapsort.c -o heapsort $ ./heapsort Sorted numbers are: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
Sanfoundry Global Education & Learning Series – 1000 C Programs.
advertisement
advertisement
Here’s the list of Best Books in C Programming, Data Structures and Algorithms.
Next Steps:
- Get Free Certificate of Merit in C Programming
- Participate in C Programming Certification Contest
- Become a Top Ranker in C Programming
- Take C Programming Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Related Posts:
- Buy Computer Science Books
- Apply for C Internship
- Apply for Computer Science Internship
- Practice Computer Science MCQs
- Watch Advanced C Programming Videos