# count swap/comparisons in sort methods

Page 1 of 1

## 3 Replies - 10239 Views - Last Post: 26 February 2011 - 10:19 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=219029&amp;s=a64bc31944892e81e22d4c702672d51f&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 dunsta

Reputation: 1
• Posts: 79
• Joined: 08-April 10

# count swap/comparisons in sort methods

Posted 26 February 2011 - 09:56 PM

Hi,
I have modified sort methods to count the number of swaps and comparisons each one does.
I have 4 methods: Bubble, Insertion, Selection and Quick sort.
Can you take a look to see if I am counting the swaps and comparisons correctly.
I will post one at a time, so I am not posting too much code at once.

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

public class IntQuickSorter
{
public static int compare =0, swap=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("Quick sort swap: "+swap+" compare: "+compare);
}

/**
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;

if (start < end)
{
// 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);
}
}

/**
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++)
{
compare++;
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];
swap++;
array[b] = temp;

}
}

```

Thanks for taking a look

Is This A Good Question/Topic? 0

## Replies To: count swap/comparisons in sort methods

### #2 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11308
• Posts: 42,590
• Joined: 27-December 08

## Re: count swap/comparisons in sort methods

Posted 26 February 2011 - 10:08 PM

You're missing a comparison here in your doQuicksort() method: if (start < end). Looks good to me otherwise.

### #3 dunsta

Reputation: 1
• Posts: 79
• Joined: 08-April 10

## Re: count swap/comparisons in sort methods

Posted 26 February 2011 - 10:18 PM

thanks macosxnerd101,
You have helped me quite a lot over the last year.
and Insertion sort...
```/**
The IntInsertionSorter class provides a public static
method for performing an insertion sort on an int array.
*/

public class IntInsertionSorter
{

/**
The insertionSort method performs an insertion sort on
an int array. The array is sorted in ascending order.
@param array The array to sort.
*/

public static void insertionSort(int[] array)
{
int swap = 0;
int compare = 0;
int unsortedValue;  // The first unsorted value
int scan;           // Used to scan the array

// The outer loop steps the index variable through
// each subscript in the array, starting at 1. This
// is because element 0 is considered already sorted.
for (int index = 1; index < array.length; index++)
{
// The first element outside the sorted subset is
// array[index]. Store the value of this element
// in unsortedValue.
unsortedValue = array[index];

// Start scan at the subscript of the first element
// outside the sorted subset.
scan = index;

// Move the first element outside the sorted subset
// into its proper position within the sorted subset.

while (scan > 0 && array[scan-1] > unsortedValue)
{
array[scan] = array[scan - 1];
scan--;
swap++;
compare++;
}

// Insert the unsorted value in its proper position
// within the sorted subset.
array[scan] = unsortedValue;
swap++;

}
System.out.println("Insertion sort swap: "+swap+" compare: "+compare);
}
}
```

### #4 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11308
• Posts: 42,590
• Joined: 27-December 08

## Re: count swap/comparisons in sort methods

Posted 26 February 2011 - 10:19 PM

Do you want to count the conditions in the loop as two comparisons or one? Looks good to me otherwise.
```while (scan > 0 && array[scan-1] > unsortedValue)

```