## Mnkyman1030

Hi,

I need to write a program that counts how many total iterations are processed in a heap sort. I wrote the program but I don't think it is working properly. I have an array 32 numbers. The sort should go through a total of 160 iterations, right? Since it is of order nlogn. 32*5 = 160. However when I run my program it is giving me 256 iterations. I don't know what is wrong with it....I've been trying for a while now and can't seem to find a way to fix it. Can someone please help! It would be greatly appreciated.

``````#include <stdio.h>
#include <iostream>
using namespace std;
int SortHeap(int[], int);
int main()
{
int i, arr_num_items;
//int count;
int arr[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,116,174,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32};
//int arr[] = {17, 45, -1, 40};
//total number of items in array.
//if you do not provide the exact number you might get unwanted results
arr_num_items = 32;
//call fnSortHeap function for (arr_num_items - 2) times.
int count = 0;
for(i=arr_num_items; i>1; i--)
{
SortHeap(arr, i - 1);
}

//print the sorted array
printf("\nThe Sorted Array\n----------------\n");
for (i = 0; i < arr_num_items; i++)
printf("%4d",arr[i]);
printf("\n");
count = SortHeap(arr, 31);
cout << count << endl;
return 0;
}

//sort heap
int SortHeap(int arr[], int arr_ubound)
{
int i,o;
int lChild, rChild, mChild, root, temp;
int count = 0;
//find the root element of the current element
root = (arr_ubound-1)/2;
//creating the heap
for(o=root;o>=0;o--)
{
for(i=root;i>=0;i--)
{
count++;
lChild = (2*i)+1;
rChild = (2*i)+2;
if ((lChild <= arr_ubound) && (rChild <= arr_ubound))
{

if(arr[rChild] >= arr[lChild])
mChild = rChild;
else
mChild = lChild;
}
else
{

if(rChild > arr_ubound)
mChild = lChild;
else
mChild = rChild;
}
//swap elements
if (arr[i] < arr[mChild])
{

temp = arr[i];
arr[i] = arr[mChild];
arr[mChild] = temp;
}
}
}
//move the max element to the end of the array
temp = arr[0];
arr[0] = arr[arr_ubound];
arr[arr_ubound] = temp;
return count;
}``````

## firstPerson 761

Lets see.

Lets just take everything in this code to be related to heap_sort.

``````for(i= 32; i>1; i--)
{
SortHeap(arr, i - 1);
}``````

I substituted 32 for arr_num_items

This is so far 31 iterations. Inside it, Lets see what sortHeap is.

``````for(o=root;o>=0;o--)
{
//removed
for(i=root;i>=0;i--)
{//removed
}
}``````

Where root starts from 15,14,13...0
Take 30 for instance. Inside heapSort there is 15 * 15 iterations
Take 29 for instance. Inside heapSort there is 14* 14iterations
//and so on

31 * 15 * 15 iterations. For the first time.
30 * 14 * 14 iterations. For the seconds time
29 * 13 * 13 iterations. For the third time
n-1 * (n-1)/2* (n-1)/2 iterations, where in this case n starts from 32 to 1