How can I count the number of element comparisons in the Quicksort algorithm?

Question

When an array of elements is given, how can I count the number of element comparisons performed by the algorithm?

It is not as simple as adding a counter to the splitting method.

private void partition(int low, int high) {
    int i = low, j = high;
    // Get the pivot element from the middle of the list
    int pivot = numbers[low + (high-low)/2];

    // Divide into two lists
    while (i <= j) {

        if (array[i] < pivot) {
            i++;
            compareCount++; //it not as easy as just adding this here
        }
        else if (numbers[j] > pivot) {
            j--;
            compareCount++;
        }

        else (i <= j) {
            exchange(i, j);
            i++;
            j--;
        }
    }

You cannot do this because it counts the comparison just made, not the comparison made when evaluating false.

I tried changing if (array[i] < pivot)to while (array[i] < pivot)(for j, too), but I feel like I'm still missing something if I do this.

Answer 1

, . , , - . / , , . / .

    public class Myclass{

    public static int compareCount = 0;

    }

    /*
    * PASS parameter comparisonMethod as following
    * 0 for ==, 1 for >, 2 for >=, 3 for < and 4 for <==
    *  Method returns true or false by doing appropriate comparison based on comparisonMethod 
    */

    public bool compare(int i, int j, int comparisonMethod)
    {
      Myclass.compareCount++;
      if(comparisionMethod ==0) return i==j?true:false;
      if(comparisionMethod ==1) return i>j?true:false;
      if(comparisionMethod ==2) return i>=j?true:false;
      if(comparisionMethod ==3) return i<j?true:false;
      if(comparisionMethod ==4) return i<=j?true:false;   
    }


    private void partition(int low, int high) {
        int i = low, j = high;
        // Get the pivot element from the middle of the list
        int pivot = numbers[low + (high-low)/2];

        // Divide into two lists
        while (compare(i, j, 4)) {

            if (compare(array[i], pivot, 3)) {
                i++;
            }
            else if (compare(numbers[j], pivot, 2)) {
                j--;
            }

            else (compare(i, j, 4)) {
                exchange(i, j);
                i++;
                j--;
            }
        }
// At the end of the logic, Myclass.compareCount wil give number of comparisons made.

Answer 2

parition , 1, . , founf , pivot ( , ), .

partition(A,p,r)
{

    pivot=A[r]; // Taking last element as pivot
    i=p;
    j=r;

    while (true)
    {

        while(A[i] < pivot && i <= r )
        {

            ++comparecounter;
            ++i;

        }

        while(A[j] >= pivot && j >= 0)
        {

            --j;
            ++comparecount;

        }

        if(i < j)
        {

            Exchange A[i] and A[j]

        }
        else
        {
            return j;
        }

countcompare , partition.This .

Answer 3

You can embed the increment of the comparison counter inside each if ...

    if ((compareCount++ != -1) && (array[i] < pivot))
    ...
    else if ((compareCount++ != -1) && (numbers[j] > pivot))
    ...
    else if ((compareCount++ != -1) &&  (i <= j))

It will always evaluate the first if clause, always return true, and always execute the second.