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);

}

}

INSERTION - Inside the while loop

HEAPSORT - Twice for each call of Heapify()

I dont think you really want comparisons of non-array elements.