Counting the number of comparisons done in Heapsort

Question

I am trying to count the number of comparisons done by heap sorting algorithm. my code is based on priority queue and I want to know where I should put the counter. here is what I have but when I try to print the counter it shows zero counts, what am I doing wrong? Thank you.

here is the heapbuild function:

#include<iostream>

vector<int> pq_keys;
void buildHeap()
{
int size = pq_keys.size();
int midIdx = (size -2)/2;
while (midIdx >= 0)
{      
    shiftRight(midIdx, size-1);     
    --midIdx;
}

and this is the function that does the comparison:

int shiftRight(int low, int high)
{
  int root = low;
  int counter=0;
  while ((root*2)+1 <= high)
    {
      int leftChild = (root * 2) + 1;
      int rightChild = leftChild + 1;
      int swapIdx = root;
      if (pq_keys[swapIdx] < pq_keys[leftChild])
    {
      counter++;
      cout<<counter;
      swapIdx = leftChild;

    }
    /*If right child exists check if it is less than current root*/
    if ((rightChild <= high) && (pq_keys[swapIdx] < pq_keys[rightChild]))
    {
    counter++;
    swapIdx = rightChild;    
    }
    /*Make the biggest element of root, left and right child the root*/
    if (swapIdx != root)
    { 
    counter++;
    int tmp = pq_keys[root];
    pq_keys[root] = pq_keys[swapIdx];
    pq_keys[swapIdx] = tmp;
    root = swapIdx;
    }
    else
    {
        break;
    }
}

return counter;

}

Answer 1

You want to increment the counter before you do the comparison. Consider this code, from your shiftRight method:

if (pq_keys[swapIdx] < pq_keys[leftChild])
{
  counter++;
  cout<<counter;
  swapIdx = leftChild;

}

That only increments the counter if the conditional is true. If pq_keys[swpIdx] >= pq_keys[leftChild], then you made the comparison without counting it. You need to change your code to be:

counter++;
if (pq_keys[swapIdx] < pq_keys[leftChild])
{
  cout<<counter;
  swapIdx = leftChild;

}

You need to do the same thing in the other two places where you count comparisons: increment the counter, then do the comparison.