Code:
#include iostream
#include conio.h
#include cstdlib
#include time.h
using namespace std;
const int LOW = 1;
const int HIGH = 100;
void max_heapify(int *a, int i, int n)
{
int j, temp;
temp = a[i];
j = 2 * i;
while (j <= n)
{
if (j < n && a[j + 1] > a[j])
j = j + 1;
if (temp > a[j])
break;
else if (temp <= a[j])
{
a[j / 2] = a[j];
j = 2 * j;
}
}
a[j / 2] = temp;
return;
}
void heapsort(int *a, int n)
{
int i, temp;
for (i = n; i >= 2; i--)
{
temp = a[i];
a[i] = a[1];
a[1] = temp;
max_heapify(a, 1, i - 1);
}
}
void build_maxheap(int *a, int n)
{
int i;
for (i = n / 2; i >= 1; i--)
{
max_heapify(a, i, n);
}
}
int main()
{
int n, i;
cout << "Enter no of elements to be sorted:";
cin >> n;
int a[n];
time_t seconds;
time(&seconds);
srand((unsigned int) seconds);
cout << "Elements are:\n";
for (i = 1; i <= n; i++)
{
a[i] = rand() % (HIGH - LOW + 1) + LOW;
cout << a[i] << " ";
}
build_maxheap(a, n);
heapsort(a, n);
cout << "\nSorted elements are:\n";
for (i = 1; i <= n; i++)
{
cout << a[i] << " ";
}
return 0;
}
Output:
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
More C++ Programs:
