Number of Comparisons in Quick Sort Program

 Write a Quick sort program that takes the last element from the partition as pivot and  find the number of comparisons with pivot element. The sorting order is ascending.

 In doing so, make three partitions as mentioned below:
      the first partition has smaller elements than pivot   
      the second partition has pivot(which include duplicates i.e. elements equal to pivot) 
      third partition has larger elements than pivot.

------------------------------Program:------------------------

public class QuickSort {
 int[] arr;
  int i, j;
  int CompCnt;
 public QuickSort(int[] a)
 {
  this.arr=a;
  i=0;
  j=0;
  CompCnt=0;
  
 }
 
 public int getComparisionCount()
 {
  return CompCnt;
 }
 
    public void sort()
    {
     quicksort(0,arr.length-1);
    }
 // 3-way partition based quick sort
 void quicksort(int l, int r)
 {
     if (r <= l) return;
  
     partition(l, r);
  
     
     quicksort( l, j);
     quicksort( i, r);
 }
  
 void partition(int l, int r)
 {
      i = l-1;
      j = r;
     int p = l-1, q = r;
     int v = arr[r];    // v is pivot
  
     while (true)
     {
         // From left, find the first element greater than
         // or equal to v. This loop will definitely terminate
         // as v is last element
         while (arr[++i] < v)   // comparison with pivot
         {
          CompCnt++;
         }
         CompCnt++; //  for while loop above
  
         // From right, find the first element smaller than or
         // equal to v
         while (v < arr[--j])  // comparison with pivot
         {   CompCnt++;
             if (j == l)
                 break;
         }
       
         CompCnt++; //  for while loop above
         // If i and j cross, then we are done
         if (i >= j) break;
  
      // Swap, so that smaller goes on left greater goes on right
         swap(i,j);
  
         // Move all same left occurrence of pivot to beginning of
         // array and keep count using p
         if (arr[i] == v)    // comparison with pivot
         {   
          
             p++;
             swap(p,i);
         }
         CompCnt++;
         // Move all same right occurrence of pivot to end of array
         // and keep count using q
         if (arr[j] == v)  // comparison with pivot
         {
          CompCnt++; 
             q--;
             swap(j,q);
         }
         CompCnt++; 
         
     }
  
     // Move pivot element to its correct index
     swap(i,r);
  
     // Move all left same occurrences from beginning
     // to adjacent to arr[i]
     j = i-1;
     for (int k = l; k < p; k++, j--)
         swap(k, j);
  
     // Move all right same occurrences from end
     // to adjacent to arr[i]
     i = i+1;
     for (int k = r-1; k > q; k--, i++)
         swap(i, k);
 }
 
 
    private void swap(int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    public String toString()
    {
     String s="";
     if(arr.length==0)
      return "";
     else if(arr.length==1)
     {
      return arr[0]+"";
     }
     else
     {
      for(int i=0;i<arr.length-1;i++)
      {
       s += arr[i]+",";
      }
      s +=arr[arr.length-1];
      return s;
     }
    }
    
    
    public static void main(String a[]){
      int[] input ={3,3,2,1,0,1,3,3,2,1,0,1};
      QuickSort qs = new QuickSort(input);
      qs.sort();
         System.out.print(qs);
//            System.out.print(" ");
//        }
}
}