C Program to Sort an Array based on Heap Sort Algorithm

«
»
This C Program sorts an array based on heap sort algorithm.

Here is source code of the C Program to sort an array based on heap sort algorithm. 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 based on heap sort algorithm(MAX heap)
  3.  */ 
  4. #include <stdio.h>
  5.  
  6. void main()
  7. {
  8.     int heap[10], no, i, j, c, root, temp;
  9.  
  10.     printf("\n Enter no of elements :");
  11.     scanf("%d", &no);
  12.     printf("\n Enter the nos : ");
  13.     for (i = 0; i < no; i++)
  14.        scanf("%d", &heap[i]);
  15.     for (i = 1; i < no; i++)
  16.     {
  17.         c = i;
  18.         do
  19.         {
  20.             root = (c - 1) / 2;             
  21.             if (heap[root] < heap[c])   /* to create MAX heap array */
  22.             {
  23.                 temp = heap[root];
  24.                 heap[root] = heap[c];
  25.                 heap[c] = temp;
  26.             }
  27.             c = root;
  28.         } while (c != 0);
  29.     }
  30.  
  31.     printf("Heap array : ");
  32.     for (i = 0; i < no; i++)
  33.         printf("%d\t ", heap[i]);
  34.     for (j = no - 1; j >= 0; j--)
  35.     {
  36.         temp = heap[0];
  37.         heap[0] = heap[j    /* swap max element with rightmost leaf element */
  38.         heap[j] = temp;
  39.         root = 0;
  40.         do 
  41.         {
  42.             c = 2 * root + 1;    /* left node of root element */
  43.             if ((heap[c] < heap[c + 1]) && c < j-1)
  44.                 c++;
  45.             if (heap[root]<heap[c] && c<j)    /* again rearrange to max heap array */
  46.             {
  47.                 temp = heap[root];
  48.                 heap[root] = heap[c];
  49.                 heap[c] = temp;
  50.             }
  51.             root = c;
  52.         } while (c < j);
  53.     } 
  54.     printf("\n The sorted array is : ");
  55.     for (i = 0; i < no; i++)
  56.        printf("\t %d", heap[i]);
  57.     printf("\n Complexity : \n Best case = Avg case = Worst case = O(n logn) \n");
  58. }

advertisement
$ cc heap.c
$ a.out
Average case 
Enter no of elements :7
 
Enter the nos : 6
5
3
1
8
7
2
Heap array : 8   6       7       1       5       3       2
The sorted array is :      1     2     3     5     6     7     8
Complexity : 
Best case = Avg case = Worst case = O(n logn) 
 
$ a.out
/* Best case 
Enter no of elements :7
 
Enter the nos : 12
10
8
9
7
4
2
Heap array : 12  10      8       9       7       4       2
The sorted array is :      2     4     7     8     9     10     12
Complexity : 
Best case = Avg case = Worst case = O(n logn) 
 
$ a.out
/* Worst case 
Enter no of elements :7
 
Enter the nos : 5
7
12
6
9
10
14
Heap array : 14  9    12      5       6       7       10
The sorted array is :  5     6     7     9     10     12     14
Complexity : 
Best case = Avg case = Worst case = O(n logn) 
*/

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

Here’s the list of Best Books in C Programming, Data-Structures and Algorithms

If you wish to look at programming examples on all topics, go to C Programming Examples.

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 & technical discussions at Telegram SanfoundryClasses.