Hello,
What is the best way to count the number of swaps required to sort an array that is sorted using the Quicksort algorithm? I put a counter in what I believe is in the correct position and the tests that I have run seem to be correct however Quicksort is so complex I do not trust my data.
Thanks,

/**
   The IntQuickSorter class provides a public static
   method for performing a QuickSort on an int array.
*/

   public class IntQuickSorter2
   {
      private static int track = 0;

   /**
      The quickSort method calls the doQuickSort method
      to sort an int array.
      @param array The array to sort.
   */

      public static void quickSort(int array[])
      {
         doQuickSort(array, 0, array.length - 1);
         System.out.println("count the swaps = " + track);
      }

   /**
      The doQuickSort method uses the QuickSort algorithm
      to sort an int array.
      @param array The array to sort.
      @param start The starting subscript of the list to sort
      @param end The ending subscript of the list to sort
   */

      private static void doQuickSort(int array[], int start, int end)
      {
         int pivotPoint;
         track ++;
         //System.out.println("count" + count);

         if (start < end)
         {
            //count += 3;
         // 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);
            //count ++;
            //System.out.println(count);
         }
      }

   /**
      The partiton method selects a pivot value in an array
      and arranges the array into two sub lists. All the
      values less than the pivot will be stored in the left
      sub list and all the values greater than or equal to
      the pivot will be stored in the right sub list.
      @param array The array to partition.
      @param start The starting subscript of the area to partition.
      @param end The ending subscript of the area to partition.
      @return The subscript of the pivot value.
   */

      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 <= end; scan++)
         {
            if (array[scan] < pivotValue)
            {
               endOfLeftList++;
               swap(array, endOfLeftList, scan);
            }
         }

      // Move the pivot value to end of the
      // left sub list.
         swap(array, start, endOfLeftList);

      // Return the subscript of the pivot value.
         return endOfLeftList;
      }

   /**
      The swap method swaps the contents of two elements
      in an int array.
      @param The array containing the two elements.
      @param a The subscript of the first element.
      @param b The subscript of the second element.
   */

      private static void swap(int[] array, int a, int b)
      {
         int temp;

         temp = array[a];
         array[a] = array[b];
         array[b] = temp;
      }
   }

Recommended Answers

All 5 Replies

the best way to count the number of swaps

Wouldn't you want to increment your counter inside of swap?

the tests that I have run seem to be correct however Quicksort is so complex I do not trust my data.

One way to validate your counting is to work out a small example by hand, and compare it to what your code is doing. It's not proof, but it is evidence.

Hello gusano79,
I believe that I put in the wrong code. I actually did have a counter in the swap method.
My apologies. :)

I have discovered that if I put an if clause in the swap method to check and see if array[a] is != to array[b] I find several instances where they actually are equal and if I don't count those with my counter the the number of viable swaps decreases. Now I have to ask myself whether or not I should consider them viable swaps or not since the computer is doing them then it is using up resources therefore they should be counted. What is your opinion?
Thanks,

if I put an if clause in the swap method to check and see if array[a] is != to array[b] I find several instances where they actually are equal and if I don't count those with my counter the the number of viable swaps decreases.
...
whether or not I should consider them viable swaps or not since the computer is doing them then it is using up resources therefore they should be counted.

As far as the swap method is concerned, I'd have it just do the swap, whether the elements are equal or not. This keeps it simple and clear--when you say "swap," you'll want it to really mean "swap," not "swap except if the elements are equal."

But that doesn't answer your question: Should you check for equality before swapping? I wouldn't. It would only matter if the swap operation was inefficient, but we're talking Java here, so any complicated data structure will be represented by a class, and you'll be swapping references to instances of that class, not the instances themselves.

And the other half of your question: Should you count swapping equal elements? If you don't check for equality, then you have to... but you'd want to even if you were checking. Counting swaps is more about the characteristics of the algorithm than it is about sorting any specific data set--if the algorithm says to swap the elements, you'll want to track it regardless.

commented: Well said +6

Thank you for your keen insight into this matter. I am suprised at how inefficient the quicksort method is compared to the insertion and selection sort. The insertion and selection sort seems to be the number of elements to sort while the quicksort seems to be 10 - times the number of elements needed to be sorted. That is with sorting 10000 numbers.

Should you check for equality before swapping?

The detailed argument depends on whether the array is of a primitive type or contains objects.
For two primitives an equals test will be trivial, and a swap pretty trivial too.
For objects you will use a Comparator to determine the sort order. That returns an int value that tells you whether the two objects are >, equal, or <, so checking for equal is just as trivial as for primitives. Swap is (as gusano said) just swapping 2 references.
So either way, testing for equal is so trivial that you shouldn't worry about the resources it uses.

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.