Hello,
What is the best way to check my code? I have written a program that counts the swaps required to sort an integer array using the Bubble, Selection, Insertion and Quick sort methods. How can I be absolutely certain that my swap counts are correct? Will someone take a look at my code and make a suggestion? Is there code on the web that will confirm my results?
Thanks,
Jim
The way to be absolutely certain about that sort of thing is called encapsulation. Wrap the thing you want to sort in a class and make it private so nothing can ever touch it except through methods that you design. If you are sorting an int array, you could do it like this:
public final class SwapIntArray {
private int count; // Encapsulated count
private final int[] content; // Encapsulated array
/** Copies the given array, so no one can touch the true content array */
public SwapIntArray(int[] content) {
this.content = java.util.Arrays.copyOf(content, content.length);
}
public int get(int index) { return content[index]; }
public int length() { return content.length; }
public int count() { return count; }
/** The only possible way to swap! */
public void swap(int index1, int index2) {
int temp = content[index1];
content[index1] = content[index2];
content[index2] = temp;
count++;
}
}
Now test your sorting algorithms by modifying them to sort your encapsulating class. Check count before and after the sort, and then there can be no doubt that the difference is the actual number of swaps. Compare the count you get this way with the count you calculate in the other way you are doing it.
Hello bguild,
This is a totally outstanding answer. I am having trouble grasping all of it but will work on it this evening. In the meantime if you don't mind I will show you my code. I am having a difficult time processing a count statement inside of the while statement inside my insertion sort method. The insertion sort method works fine running by itself in its own program but inside this program the swap ++; and the println(swap); are not doing anything? Is this what you mean by needing to encapsulate? Thank you so much. Hank
import java.util.Random; // Needed for the Random class
import java.util.Scanner; // Needed for the Scanner class
/**
This program tests the bubbleSort method in the
IntBubbleSorter class.
*/
public class SortingBenchmarks3
{
private static int track = 0;
private static int flips = 0;
private static int change = 0;
public static void main(String[] args)
{
// Create an int array with test values.
int[] values = {5, 1, 3, 6, 4, 2};
int listSize = 0; // Size of list.
int swapCount = 0;
// Create a Scanner object for keyboard input.
Scanner keyboard = new Scanner(System.in);
System.out.println("This program compares how many" +
" exchanges it takes \nfor 4 - different searching" +
" algorithms to sort \na list of up to 100 integers." +
" Those searching \nalgorithms are named \n'Bubble Sort'," +
" 'Selection Sort', 'Insertion Sort' and 'Quick Sort.'" );
System.out.println();
System.out.println("Lets start by creating a list of numbers.");
System.out.println();
//do
//{
//System.out.println("Please enter an integer from 2 to 100: ");
//listSize = keyboard.nextInt();
//}
//while (listSize < 2 || listSize > 100);
//values = new int[listSize];
//buildList(values);
// Display the array's contents.
//System.out.println("Original order: ");
//for (int element : values)
//System.out.print(element + " ");
//System.out.println();
// Sort the array.
bubbleSort(values);
// Sort the array.
selectionSort(values);
// Sort the array.
insertionSort(values);
// Sort the array.
quickSort(values);
}
/**
The IntBubbleSorter class provides a public static
method for performing a bubble sort on an int array.
*/
/**
The buildList method builds a random list.
@param array The array to build.
*/
public static void buildList(int[] array)
{
int index;
Random randomNumbers = new Random();
for (index = 0; index <= array.length - 1; index++)
{
array[index] = randomNumbers.nextInt(100);
}
// Display the array's contents.
System.out.println("Original order: ");
for (int element : array)
System.out.print(element + " ");
System.out.println();
}
/**
The IntBubbleSorter class provides a public static
method for performing a bubble sort on an int array.
*/
/**
The bubbleSort method uses the bubble sort algorithm
to sort an int array.
@param array The array to sort.
*/
public static void bubbleSort(int[] array)
{
int lastPos; // Position of last element to compare
int index; // Index of an element to compare
int temp; // Used to swap to elements
int swap = 0; // Number of swaps
System.out.println();
System.out.println("This is an example of the"
+ " Bubble Sort algorithm.");
System.out.println();
// The outer loop positions lastPos at the last element
// to compare during each pass through the array. Initially
// lastPos is the index of the last element in the array.
// During each iteration, it is decreased by one.
for (lastPos = array.length - 1; lastPos >= 0; lastPos--)
{
// The inner loop steps through the array, comparing
// each element with its neighbor. All of the elements
// from index 0 thrugh lastPos are involved in the
// comparison. If two elements are out of order, they
// are swapped.
for (index = 0; index <= lastPos - 1; index++)
{
// Compare an element with its neighbor.
if (array[index] > array[index + 1])
{
// Swap the two elements.
temp = array[index];
array[index] = array[index + 1];
array[index + 1] = temp;
swap ++;
}
}
}
// Display the array's contents.
System.out.println("\nSorted order: ");
for (int element : array)
System.out.print(element + " ");
System.out.println();
System.out.println();
System.out.println("The Bubble Sort algorithm" +
" made " + swap + " exchanges." );
//return swap;
}
/**
The selectionSort method performs a selection sort on an
int array. The array is sorted in ascending order.
@param array The array to sort.
*/
public static void selectionSort(int[] array)
{
int startScan; // Starting position of the scan
int index; // To hold a subscript value
int minIndex; // Element with smallest value in the scan
int minValue; // The smallest value found in the scan
int swap = 0;
System.out.println();
System.out.println("This is an example of the"
+ " Selection Sort algorithm.");
System.out.println();
// The outer loop iterates once for each element in the
// array. The startScan variable marks the position where
// the scan should begin.
for (startScan = 0; startScan < (array.length-1); startScan++)
{
// Assume the first element in the scannable area
// is the smallest value.
minIndex = startScan;
minValue = array[startScan];
// Scan the array, starting at the 2nd element in
// the scannable area. We are looking for the smallest
// value in the scannable area.
for(index = startScan + 1; index < array.length; index++)
{
if (array[index] < minValue)
{
minValue = array[index];
minIndex = index;
}
}
// Swap the element with the smallest value
// with the first element in the scannable area.
array[minIndex] = array[startScan];
array[startScan] = minValue;
swap ++;
//System.out.println("flips");
//System.out.println("Friends");
}
flips += swap;
System.out.println();
System.out.println();
//System.out.println("The Selection Sort algorithm" +
// " made " + swap + " exchanges." );
System.out.println("Selection sort " + flips);
// Display the array's contents.
//System.out.println("\nSelection sorted order: ");
//for (int element : array)
//System.out.print(element + " ");
}
/**
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 unsortedValue; // The first unsorted value
int scan; // Used to scan the array
int swap = 0;
// The outer loop steps the index variable through
// each subscript in the array, starting at 1. The portion of
// the array containing element 0 by itself is already sorted.
for (int index = 1; index < array.length; index++)
{
// The first element outside the sorted portion 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 part.
scan = index;
// Move the first element in the still unsorted part
// into its proper position within the sorted part.
while (scan > 0 && array[scan-1] > unsortedValue)
{
array[scan] = array[scan - 1];
scan--;
//swap += 1;
//System.out.println(swap);
//change ++;
//System.out.println("Friends");
}
swap ++;
//change += swap;
// Insert the unsorted value in its proper position
// within the sorted subset.
array[scan] = unsortedValue;
//swap++;
}
// Display the array's contents.
//System.out.println("\nInsertion sorted order: ");
//for (int element : array)
//System.out.print(element + " ");
//System.out.println();
System.out.print("insertion sort change " + change);
System.out.println("insertion sort swap " + swap);
}
/**
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);
// Display the array's contents.
System.out.println("\nQuick sorted order: ");
for (int element : array)
System.out.print(element + " ");
System.out.println();
System.out.println("Quick sort " + track);
//System.out.println(swap + "insertion");
}
/**
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;
int count = 0;
count ++;
track += count;
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
int count = 0;
// 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);
//count ++;
// 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);
//count ++;
}
}
// Move the pivot value to end of the
// left sub list.
swap(array, start, endOfLeftList);
//count ++;
//System.out.println(count);
// 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;
}
}
I notice that you sort the same array 4 times. This puts bubble sort at a huge disadvantage because it is the only one that has to sort an unsorted list. Once bubble sort is finished, the rest of the sorts will find the array pre-sorted, which should greatly reduce the required swaps.
Wow, I definitely did did'nt I. Thanks for the help with these two issues.
Jim
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.