title: How to count comparisons and swaps in quicksort?
body: <pre><code>public class IntQuickSorter
  {
     public static int numOfComps = 0,
                       numOfSwaps = 0;
  
      public static void main(String[] args)
     {
        // Create an int array with test values.
        int[] values = { 1, 2, 3, 4, 5,  6 };
        //int[] values = { 5, 1, 3, 6, 4, 2 };
        //int[] values = { 5, 7, 2, 8, 9, 1 };
  
          System.out.println("\n\nQuick Sort:");
  
        // Display the array's contents.
        System.out.println("\nOriginal order: ");
        for (int element : values)
           System.out.print(element + " ");
  
        // Sort the array.
        quickSort(values);
  
        //System.out.println("\n\nNumber of comps = " + numOfComps);
        //System.out.println("Number of swaps = " + numOfSwaps);
  
        // Display the array's contents.
        System.out.println("\nSorted order: ");
        for (int element : values)
           System.out.print(element + " ");
  
        System.out.println();
     }
  
     public static void quickSort(int array[])
     {
        doQuickSort(array, 0, array.length - 1);
        System.out.println("\n\nNumber of comps = " + numOfComps);
         System.out.println("Number of swaps = " + numOfSwaps);
     }
  
     private static void doQuickSort(int array[], int start, int end)
     {
        int pivotPoint;
  
        if (start &lt; end)
        {
           numOfComps++;
  
           // Get the pivot point.
           pivotPoint = partition(array, start, end);
  
           // Sort the first sub list.
           doQuickSort(array, start, pivotPoint - 1);
  
           // Sort the second sub list.
           doQuickSort(array, pivotPoint + 1, end);
        }
     }
  
     private static int partition(int array[], int start, int end)
     {
        int pivotValue;    // To hold the pivot value
        int endOfLeftList; // Last element in the left sub list.
        int mid;           // To hold the mid-point subscript
  
        // Find the subscript of the middle element.
        // This will be our pivot value.
        mid = (start + end) / 2;
  
        // Swap the middle element with the first element.
        // This moves the pivot value to the start of 
        // the list.
        swap(array, start, mid);
  
        // Save the pivot value for comparisons.
        pivotValue = array[start];
  
        // For now, the end of the left sub list is
        // the first element.
        endOfLeftList = start;
  
        // Scan the entire list and move any values that
        // are less than the pivot value to the left
        // sub list.
        for (int scan = start + 1; scan &lt;= end; scan++)
        {
  
           if (array[scan] &lt; pivotValue)
           {
              endOfLeftList++;
              swap(array, endOfLeftList, scan);
  
                  numOfSwaps ++;
           }
           numOfComps++;
        }
  
        // Move the pivot value to end of the
        // left sub list.
        swap(array, start, endOfLeftList);
  
        // Return the subscript of the pivot value.
        return endOfLeftList;
     }
  
     private static void swap(int[] array, int a, int b)
     {
        int temp;
  
           temp = array[a];
           array[a] = array[b];
           array[b] = temp;
      }
  }
  </code></pre>
  
  <p>How do I code this quicksort program in Java to count the number of comparisons and the number of swaps? Where I have the swap code now, it counts swaps even with a sorted array of numbers and it shouldn't. And is the comparison code in the right place? Thanks for any help.</p>