Solved
Count comparisons in sort algorithms??
Posted on 2003-10-27
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);
}
}