# Count comparisons in sort algorithms??

I'm interested in tracking the number of comparisons in some sort algorithms to compare them.
Im not exactly sure where this counter need to be incremented.  If anyone has any help, thanks.
Some of the sorts I am using include the following.

INSERTION
-------------------------------------------------------------------------------------
template <class T>
void InsertionSort(T A[], int size)
{
for(int j=1; j<size; j++)
{
T key = A[j];
int i = j - 1;
while ((i >= 0) && (A[i] > key))
{
A[i+1] = A[i];
i -= 1;
}
A[i+1] = key;
}
}

HEAPSORT
------------------------------------------------------------------------------
template <class T>
void Heapsort(T A[], int size)
{
BuildHeap(A, size);
for(i=size; i>1; i--)
{
int tmp = A[0];
A[0] = A[i-1];
A[i-1] = tmp;
size--;
Heapify(A, 1, size);
}
}

template <class T>
void BuildHeap(T A[], int size)
{
for(i=size/2; i>0; i--)
Heapify(A, i, size);
}

template <class T>
void Heapify(T A[], int i, int size)
{
int  l = 2 * i;
int  r = 2 * i + 1;
int largest = 0;

if(l <= heapsize && A[l-1] > A[i-1])
largest = l;
else
largest = i;

if(r <= heapsize && A[r-1] > A[largest-1])
largest = r;
if(largest != i)
{
int tmp = A[i-1];
A[i-1] = A[largest-1];
A[largest-1] = tmp;
Heapify(A, largest, heapsize);
}
}

###### Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
Um, you would need to increment a counter everytime you compare elements in the array.

INSERTION - Inside the while loop
HEAPSORT - Twice for each call of Heapify()

I dont think you really want comparisons of non-array elements.
Author Commented:
So if I were to place a counter in the heapify function, is there a way I can use that in the original heapsort function in order to produce output after heapsort is done running?
Does this run into making the variable global? If so how is this done?
Commented:
There are many ways you could do it:
1. Use a global variable to count the number of comparisons
2. Create a property for the class and use that to store the count
3. Return the count from the Heapify function

Decide what you're after and have a go. Im not inclined to do too much until I can see you're trying to figure it out.
Author Commented:
I guess im confused, sorry :(  I modofied it to return the compares??

HEAPSORT
------------------------------------------------------------------------------
template <class T>
void Heapsort(T A[], int size)
{
BuildHeap(A, size);
for(i=size; i>1; i--)
{
int tmp = A[0];
A[0] = A[i-1];
A[i-1] = tmp;
size--;
Heapify(A, 1, size);
}
}

template <class T>
void BuildHeap(T A[], int size)
{
for(i=size/2; i>0; i--)
Heapify(A, i, size);
}

template <class T>
void Heapify(T A[], int i, int size)
{
int compares;
comapres +=2;
int  l = 2 * i;
int  r = 2 * i + 1;
int largest = 0;

if(l <= heapsize && A[l-1] > A[i-1])
largest = l;
else
largest = i;

if(r <= heapsize && A[r-1] > A[largest-1])
largest = r;
if(largest != i)
{
int tmp = A[i-1];
A[i-1] = A[largest-1];
A[largest-1] = tmp;
Heapify(A, largest, heapsize);
}
return compares;
}
Commented:
You declared the int compares locally inside the Heapify function. This means that when the function exits, that variable is wiped out. To return it successfully, you need to modify the function declaration to return an int rather than a void.

Since you call the Heapify function recursively, you should capture the return value of the Heapify (A, largest, heapsize) call and add that to you compares counter before returning it.

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Author Commented:
Well I cant declare it in the heapsort() function because heapify is called both from buildheap and heapsort right?

If I capture it only from Heapify(A, largest, heapsize) won't that make the count on compares inaccurate?

Well sorry for the additional questions, i'm just very confused on how this is done.  If I didnt mention im a beginning programmer so some things that are basically obvious to advanced programmers, are kinda new to me.

Thanks for your continued help.

Ben

Commented:
This is what im thinking, although there are other ways to do it.

template <class T>
void Heapsort(T A[], int size)
{
int count;
count = BuildHeap(A, size);
for(i=size; i>1; i--)
{
int tmp = A[0];
A[0] = A[i-1];
A[i-1] = tmp;
size--;
count += Heapify(A, 1, size);
}
printf("count = %d\n",count);
}

template <class T>
int BuildHeap(T A[], int size)
{
int count=0;
for(i=size/2; i>0; i--)
count += Heapify(A, i, size);
return count;
}

template <class T>
int Heapify(T A[], int i, int size)
{
int count;
count +=2;
int  l = 2 * i;
int  r = 2 * i + 1;
int largest = 0;

if(l <= heapsize && A[l-1] > A[i-1])
largest = l;
else
largest = i;

if(r <= heapsize && A[r-1] > A[largest-1])
largest = r;
if(largest != i)
{
int tmp = A[i-1];
A[i-1] = A[largest-1];
A[largest-1] = tmp;
count += Heapify(A, largest, heapsize);
}
return count;
}
###### It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C++

From novice to tech pro — start learning today.