C Program to Implement Heap Sort

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.

  1. /*
  2.  * C Program to sort an array using Heap Sort technique
  3.  */
  4.  
  5. #include<stdio.h>
  6. #include <stdlib.h>
  7. #define MAX 25
  8.  
  9. void random_shuffle(int arr[])
  10. {
  11.     int i, j, temp;
  12.     srand(time(NULL));
  13.     for (i = MAX - 1; i > 0; i--) {
  14.          j = rand()%(i + 1);
  15.          temp = arr[i];
  16.          arr[i] = arr[j];
  17.          arr[j] = temp;
  18.     }
  19. }
  20. void  max_heapify(int a[], int i, int heapsize)
  21. {
  22.     int tmp, largest;
  23.     int l = (2 * i) + 1;
  24.     int r = (2 * i) + 2;
  25.     if ((l <= heapsize) && (a[l] > a[i]))
  26.          largest = l;
  27.     else
  28.          largest = i;
  29.     if ((r <= heapsize) && (a[r] > a[largest]))
  30.          largest = r ;
  31.     if (largest != i) 
  32.     {
  33.          tmp = a[i];
  34.          a[i] = a[largest];
  35.          a[largest] = tmp;
  36.          max_heapify(a, largest, heapsize);
  37.     }
  38.  
  39. }
  40. void  build_max_heap(int a[], int heapsize)
  41. {
  42.     int i;
  43.     for (i = heapsize/2; i >= 0; i--)
  44.     {
  45.          max_heapify(a, i, heapsize);
  46.     }
  47.  
  48. }
  49. void heap_sort(int a[], int heapsize)
  50. {
  51.     int i, tmp;
  52.     build_max_heap(a, heapsize);
  53.     for (i = heapsize; i > 0; i--) 
  54.     {
  55.         tmp = a[i];
  56.         a[i] = a[0];
  57.         a[0] = tmp;
  58.         heapsize--;
  59.         max_heapify(a, 0, heapsize);
  60.     }
  61. }
  62. int main()
  63. {
  64.     int i, r, heapsize;
  65.     int a[MAX];
  66.     for (i = 0; i < MAX; i++)
  67.         a[i] = i;
  68.     heapsize = MAX - 1;
  69.     random_shuffle(a);
  70.     printf("\n");
  71.     heap_sort(a, heapsize);
  72.     for (i = 0; i < MAX; i++)
  73.         printf("%d ", a[i]);
  74.     return 0;
  75. }

$ 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.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.