I'm trying to figure out where a proper place to put a comparison counter to count the number of 'comparisons' made in a quick sort is. This is my code so far, I have one counter where I think it should go, but I'm not sure if it should place it in more than one location:

void partition(vector<int>& array, int first, int last, int &pivotIndex, int &comparisons)
{  
  int pivot = array[first];
  
  int lastS1 = first;
  int firstUnknown = first +1;
  
  for (; firstUnknown <= last; ++firstUnknown)
  {
    //comparisons++;
    if(array[firstUnknown] < pivot)
    {
    ++lastS1;
    swap(array[firstUnknown], array[lastS1]);
    comparisons++;
    }  
  }
  swap(array[first], array[lastS1]);
  pivot = lastS1;

}

Any help would be appreciated! Thanks in advance!

Recommended Answers

All 3 Replies

It looks to me as though you're currently counting swaps, not comparisons. To count comparisons, you need to move your line 15 outside the if statement.

Also, note that you're not initializing comparisons, so if your function is passed a non-zero argument, your count will be off by that amount.

Thanks! I'm just having a hard time determining what 'comparisons' means compared to swaps, since one usually follows the other. Do you think the counter should be at line 10? I imagine it should be within the for loop. The program reads from various files and initializes comparisons to 0 each time a new file and subsequent set of numbers is made, so I think that is fine right?

Sorry it took me so long to reply; for some reason, the email informing me of your post was marked as spam.

Yes, you want to move the incrementer outside of the if statement (before or after doesn't matter). Your if statement is testing for comparisons; it's testing for matches, right? So, it doesn't make sense to only increment the comparison counter in there.

And, if comparisons can be trusted to be reset when your function gets it, it's OK not to initialize it, though I still would.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.