Counting Heap Sort Iterations

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

[mrnutty]

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

this leads to
31! * 15! * 15 ! = REALLY big number of iterations.