0

Hi, I am trying to count the number of iterations that the heap sort goes through but for some reason when my program hits an error and aborts at the end. I don't know if I have my count in the wrong place in the for loop either. I would really appreciate the help. Thanks.

#include <stdio.h>
#include <iostream>
using namespace std;
int SortHeap(int[], int);
int main()
{
	int i, arr_num_items;
	int count;
	//int arr[] = {7,10,25,17,23,27,16,19,37,42,4,33,1,5,11};
	int arr[] = {17, 45, -1, 40, 39};
	//total number of items in array.
    //if you do not provide the exact number you might get unwanted results
    arr_num_items = 5;
	//call fnSortHeap function for (arr_num_items - 2) times.
    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, arr_num_items);
	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;
}
2
Contributors
1
Reply
2
Views
8 Years
Discussion Span
Last Post by jencas
0

I just took a short glance at your code. The second call to SortHeap works on an already sorted array, so maybe it's better to sum up the return values of the first call

int main()
{
	int i, arr_num_items;
	int count;
	//int arr[] = {7,10,25,17,23,27,16,19,37,42,4,33,1,5,11};
	int arr[] = {17, 45, -1, 40, 39};
	//total number of items in array.
    //if you do not provide the exact number you might get unwanted results
    arr_num_items = 5;
	//call fnSortHeap function for (arr_num_items - 2) times.
    int count = 0;
    for(i=arr_num_items; i>1; i--)
   	{
   		count += 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");
	cout << count << endl;
	return 0;
}
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.