C++ Program to Sort of 10 Elements Using Heap Sort Algorithm

«
»
This is a C++ Program to sort given numbers using heap sort algorithm. Heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like that algorithm, it divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the smallest element and moving that to the sorted region. The improvement consists of the use of a heap data structure rather than a linear-time search to find the minimum.

Here is source code of the C++ Program to Sort an Array of 10 Elements Using 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 Implement Heap Sort
  3.  */
  4. #include <iostream>
  5. #include <conio.h>
  6. #include <cstdlib>
  7. #include <time.h>
  8.  
  9. using namespace std;
  10.  
  11. const int LOW = 1;
  12. const int HIGH = 100;
  13.  
  14. void max_heapify(int *a, int i, int n)
  15. {
  16.     int j, temp;
  17.     temp = a[i];
  18.     j = 2 * i;
  19.     while (j <= n)
  20.     {
  21.         if (j < n && a[j + 1] > a[j])
  22.             j = j + 1;
  23.         if (temp > a[j])
  24.             break;
  25.         else if (temp <= a[j])
  26.         {
  27.             a[j / 2] = a[j];
  28.             j = 2 * j;
  29.         }
  30.     }
  31.     a[j / 2] = temp;
  32.     return;
  33. }
  34. void heapsort(int *a, int n)
  35. {
  36.     int i, temp;
  37.     for (i = n; i >= 2; i--)
  38.     {
  39.         temp = a[i];
  40.         a[i] = a[1];
  41.         a[1] = temp;
  42.         max_heapify(a, 1, i - 1);
  43.     }
  44. }
  45. void build_maxheap(int *a, int n)
  46. {
  47.     int i;
  48.     for (i = n / 2; i >= 1; i--)
  49.     {
  50.         max_heapify(a, i, n);
  51.     }
  52. }
  53. int main()
  54. {
  55.     int n, i;
  56.     cout << "Enter no of elements to be sorted:";
  57.     cin >> n;
  58.     int a[n];
  59.     time_t seconds;
  60.     time(&seconds);
  61.     srand((unsigned int) seconds);
  62.     cout << "Elements are:\n";
  63.     for (i = 1; i <= n; i++)
  64.     {
  65.         a[i] = rand() % (HIGH - LOW + 1) + LOW;
  66.         cout << a[i] << " ";
  67.     }
  68.     build_maxheap(a, n);
  69.     heapsort(a, n);
  70.     cout << "\nSorted elements are:\n";
  71.     for (i = 1; i <= n; i++)
  72.     {
  73.         cout << a[i] << " ";
  74.     }
  75.     return 0;
  76. }

Output:

advertisement
$ g++ HeapSort.cpp
$ a.out
 
Enter no of elements to be sorted: 20
Elements are:
46 81 76 98 55 30 58 57 71 57 21 65 51 68 70 63 93 53 78 53 
Sorted elements are:
21 30 46 51 53 53 55 57 57 58 63 65 68 70 71 76 78 81 93 98 
 
Enter no of elements to be sorted: 10
Elements are:
6 64 84 52 49 32 28 93 39 13 
Sorted elements are:
6 13 28 32 39 49 52 64 84 93 
 
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement

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

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.