C Program Create a program that implements a heap sortto asc

C++ Program: Create a program that implements a heap sort(to ascending order). Sort the three input arrays

1) 14,12,5,2,1,3,4,11,13,15

2) 10,9,8,7,6,5,4,3,2,1

3)1,2,3,4,5,6,7,8,9,10,11,12,13,14,15

Solution

Heap sort is not a Stable sort, and requires a constant space for sorting a list.

But Its an improved selection sort and it has improved worst-case O(n log n) runtime.

there are mainly 2 steps for this

1) Build the heap

2) Sort the heap

Build Heap

Sort the heap

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 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;
}

please try calling these function from this main function
build your own array as in question and print the sorted out put by looping the same.

int main()
{
int n, i, x;
cout<<\"enter no of elements of array\ \";
cin>>n;
int a[20];
for (i = 1; i <= n; i++)
{
cout<<\"enter element\"<<(i)<<endl;
cin>>a[i];
}
build_maxheap(a,n);
heapsort(a, n);
cout<<\"sorted output\ \";
for (i = 1; i <= n; i++)
{
cout<<a[i]<<endl;
}
getch();
}