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;
}
}
``````
3
Contributors
5
Replies
18
Views
5 Years
Discussion Span
Last Post by JamesCherrill

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.