Outline
* Sorting
The discussion was spent reviewing, and answering various questions about, sorting.
Coverage of sorting can be found elsewhere (including the book), so I have omitted it here. Below are the sorting algorithm implementations I wrote up and handed out at the beginning of discussion. Also check out Discussion 9, the midterm review session, for information on some of (what I consider) the more important aspects of the algorithms, and further analysis on some of the questions that came up during this discussion.
Algorithm Implementations and Testing/Timing Infrastructure
Below is a general sorting, testing, and timing infrastructure and implementations of all of the sorting algorithms we have covered (except Quicksort, which you will do for proj2). I wrote this code as a way to become familiar (once again) with sorting (and I suggest you do the same) and to provide you with more readable code than is found in the book. Although you may not copy this code (as doing so would be plagiarism and cheating), you may use it as a reference.
The abstract Sorter class is superclass to all specific sorting implementation classes. It provides helpful utility methods (presently this is limited to the printArray() method) and gurantees that each implementation has the same basic interface (specifically, sort() and getSortName()).
public abstract class Sorter
{
public static final boolean DEBUG = true;
public static void printArray(int[] numbers)
{
final String DELIMITER = " ";
for (int currentIndex = 0;
currentIndex < numbers.length;
currentIndex ++)
{
System.out.print(numbers[currentIndex] + DELIMITER);
}
System.out.println();
}
public abstract int[] sort(int[] numbers);
public abstract String getSortName();
}
The SortTests class provides a general infrastructure for running a variable set of Sorter implementations (ie sorting algorithms) with a variable set of inputs (including short, sorted, reverse sorted, and random arrays). The output of these sorts is then automatically verified against a know good implementation (java.util.Array.sort()) and the user is notified if there is a problem. This is a good example of automated testing that you might find useful in testing your own implementations. Finally, there is potential to include timing code (for real world measurements) in this infrastructure. I may add this feature at some point in the future.
import java.util.Arrays;
import java.util.Random;
public class SortTests
{
public static final int BASIC_TEST_COUNT = 2;
public static final int SORTED_TEST_COUNT = 1;
public static final int REVERSE_SORTED_TEST_COUNT = 1;
public static final int SORTED_ARRAY_MAX_LENGTH = 20;
public static final int RANDOM_TEST_COUNT = 1;
public static final int RANDOM_ARRAY_MAX_LENGTH = 20;
public static final int RANDOM_MAX_VALUE = 100;
public static void main(String[] args)
{
Sorter[] sorts =
{
new WorstInsertionSort(),
new MediumInsertionSort(),
new BestInsertionSort(),
new ShellSort(),
new SelectionSort(),
new MergeSort(),
new QuickSort()
};
Sorter referenceSort = new JavaSort();
//TODO - Add timing code
int inputs[][] = new int[
BASIC_TEST_COUNT + SORTED_TEST_COUNT +
REVERSE_SORTED_TEST_COUNT + RANDOM_TEST_COUNT
][];
// Basic tests
inputs[0] = new int[0];
inputs[1] = new int[1];
inputs[1][0] = 5;
Random numberGenerator = new Random();
for (int currentSortedTestNumber = 0;
currentSortedTestNumber < SORTED_TEST_COUNT;
currentSortedTestNumber ++)
{
int[] sortedArray = new int[
numberGenerator.nextInt(SORTED_ARRAY_MAX_LENGTH)];
for (int currentSortedArrayIndex = 0;
currentSortedArrayIndex < sortedArray.length;
currentSortedArrayIndex ++)
{
sortedArray[currentSortedArrayIndex] =
currentSortedArrayIndex;
}
inputs[BASIC_TEST_COUNT + currentSortedTestNumber] =
sortedArray;
}
for (int currentReverseSortedTestNumber = 0;
currentReverseSortedTestNumber < REVERSE_SORTED_TEST_COUNT;
currentReverseSortedTestNumber ++)
{
int[] reverseSortedArray = new int[
numberGenerator.nextInt(SORTED_ARRAY_MAX_LENGTH)];
for (int currentReverseSortedArrayIndex = 0;
currentReverseSortedArrayIndex < reverseSortedArray.length;
currentReverseSortedArrayIndex ++)
{
reverseSortedArray[currentReverseSortedArrayIndex] =
((reverseSortedArray.length - 1) -
currentReverseSortedArrayIndex);
}
inputs[BASIC_TEST_COUNT + SORTED_TEST_COUNT +
currentReverseSortedTestNumber] = reverseSortedArray;
}
for (int currentRandomTestNumber = 0;
currentRandomTestNumber < RANDOM_TEST_COUNT;
currentRandomTestNumber ++)
{
int[] randomArray = new int[
numberGenerator.nextInt(RANDOM_ARRAY_MAX_LENGTH)];
for (int currentRandomArrayIndex = 0;
currentRandomArrayIndex < randomArray.length;
currentRandomArrayIndex ++)
{
randomArray[currentRandomArrayIndex] =
numberGenerator.nextInt(RANDOM_MAX_VALUE);
}
inputs[BASIC_TEST_COUNT + SORTED_TEST_COUNT +
REVERSE_SORTED_TEST_COUNT + currentRandomTestNumber] =
randomArray;
}
for (int currentInputIndex = 0;
currentInputIndex < inputs.length;
currentInputIndex ++)
{
System.out.println();
System.out.println("===== Looking at input #" +
currentInputIndex + " =====");
int[] currentInput = inputs[currentInputIndex];
int[] referenceInputCopy = new int[currentInput.length];
System.arraycopy(currentInput, 0,
referenceInputCopy, 0,
currentInput.length);
int[] referenceOutput = referenceSort.sort(referenceInputCopy);
for (int currentSortIndex = 0;
currentSortIndex < sorts.length;
currentSortIndex ++)
{
Sorter currentSort = sorts[currentSortIndex];
System.out.println("--- Looking at sorter \'" +
currentSort.getSortName() + "\' ---");
// The sorting algorithms modify the array passed in,
// so we need to make a new copy for each sorter
int[] inputCopy = new int[currentInput.length];
System.arraycopy(currentInput, 0,
inputCopy, 0,
currentInput.length);
int[] sortOutput = currentSort.sort(inputCopy);
if (!(Arrays.equals(sortOutput, referenceOutput)))
{
System.out.println("!!! Reference sorter and " +
currentSort.getSortName() +
" have different output!");
System.out.println("!!! Output from " + currentSort.getSortName() + ":");
Sorter.printArray(sortOutput);
}
}
}
}
}
JavaSort is the known-good reference implementation.
import java.util.Arrays;
public class JavaSort extends Sorter
{
public String getSortName()
{
return "JavaSort";
}
public int[] sort(int[] numbers)
{
if (DEBUG)
{
System.out.println("Entering " + getSortName() + " with:");
printArray(numbers);
}
// This is the best kind of sort
Arrays.sort(numbers);
if (DEBUG)
{
System.out.println("Exiting " + getSortName() + " with:");
printArray(numbers);
}
return numbers;
}
}
I have provided three versions of Insertion sort.
The first, WorstInsertionSort, always runs in O(n^2).
public class WorstInsertionSort extends Sorter
{
public String getSortName()
{
return "WorstInsertionSort";
}
public int[] sort(int[] numbers)
{
if (DEBUG)
{
System.out.println("Entering " + getSortName() + " with:");
printArray(numbers);
}
if (numbers.length <= 1)
{
return numbers;
}
for (int currentPassNumber = 0;
currentPassNumber < (numbers.length - 1);
currentPassNumber ++)
{
for (int currentIndex = 0;
currentIndex < (numbers.length - 1);
currentIndex ++)
{
if (numbers[currentIndex] > numbers[currentIndex + 1])
{
int temp = numbers[currentIndex + 1];
numbers[currentIndex + 1] = numbers[currentIndex];
numbers[currentIndex] = temp;
}
}
}
if (DEBUG)
{
System.out.println("Exiting " + getSortName() + " with:");
printArray(numbers);
}
return numbers;
}
}
The second runs in ~(n^2 / 2) = O(n^2).
public class MediumInsertionSort extends Sorter
{
public String getSortName()
{
return "MediumInsertionSort";
}
public int[] sort(int[] numbers)
{
if (DEBUG)
{
System.out.println("Entering " + getSortName() + " with:");
printArray(numbers);
}
if (numbers.length <= 1)
{
return numbers;
}
for (int upperIndex = (numbers.length - 1);
upperIndex > 0;
upperIndex --)
{
for (int currentIndex = 0;
currentIndex < upperIndex;
currentIndex ++)
{
if (numbers[currentIndex] > numbers[currentIndex + 1])
{
int temp = numbers[currentIndex + 1];
numbers[currentIndex + 1] = numbers[currentIndex];
numbers[currentIndex] = temp;
}
}
}
if (DEBUG)
{
System.out.println("Exiting " + getSortName() + " with:");
printArray(numbers);
}
return numbers;
}
}
The final version runs in O(n) with already-sorted input and O(n^2) otherwise. This is the version you should always use (although analyzing the other versions is an interesting exercise).
public class BestInsertionSort extends Sorter
{
public String getSortName()
{
return "BestInsertionSort";
}
public int[] sort(int[] numbers)
{
if (DEBUG)
{
System.out.println("Entering " + getSortName() + " with:");
printArray(numbers);
}
if (numbers.length <= 1)
{
return numbers;
}
for (int upperIndex = 1;
upperIndex < numbers.length;
upperIndex ++)
{
int currentIndex = upperIndex;
// I like to use a while loop:
// This will only happen /while/ it needs to
// This is an example of short circuiting -
// We wont hit the second part (which may lead to an array index
// out of bounds) if the first part fails.
while ((currentIndex > 0) &&
(numbers[currentIndex] < numbers[currentIndex - 1]))
{
int temp = numbers[currentIndex - 1];
numbers[currentIndex - 1] = numbers[currentIndex];
numbers[currentIndex] = temp;
currentIndex --;
}
}
if (DEBUG)
{
System.out.println("Exiting " + getSortName() + " with:");
printArray(numbers);
}
return numbers;
}
}
public class SelectionSort extends Sorter
{
public String getSortName()
{
return "SelectionSort";
}
public int[] sort(int[] numbers)
{
if (DEBUG)
{
System.out.println("Entering " + getSortName() + " with:");
printArray(numbers);
}
if (numbers.length <= 1)
{
return numbers;
}
for (int currentFillIndex = 0;
// Here we don't have to go to numbers.length because we
// get one for free "by elimination"
currentFillIndex < (numbers.length - 1);
currentFillIndex ++)
{
int lowestNumberFound = numbers[currentFillIndex];
int lowestNumberIndex = currentFillIndex;
for (int currentSearchIndex = (currentFillIndex + 1);
currentSearchIndex < numbers.length;
currentSearchIndex ++)
{
// Could also swap the number at the currentFillIndex
// with the lowest number each time we find a lowest number
// Would probably be even more expensive
if (numbers[currentSearchIndex] < lowestNumberFound)
{
lowestNumberFound = numbers[currentSearchIndex];
lowestNumberIndex = currentSearchIndex;
}
}
// Could only do the following if we are actually swapping
// the number at the fill index out (for swap counting).
int temp = numbers[currentFillIndex];
numbers[currentFillIndex] = lowestNumberFound;
numbers[lowestNumberIndex] = temp;
}
if (DEBUG)
{
System.out.println("Exiting " + getSortName() + " with:");
printArray(numbers);
}
return numbers;
}
}
public class ShellSort extends Sorter
{
public String getSortName()
{
return "ShellSort";
}
public int[] sort(int[] numbers)
{
if (DEBUG)
{
System.out.println("Entering " + getSortName() + " with:");
printArray(numbers);
}
if (numbers.length <= 1)
{
return numbers;
}
// Can switch this out with another gap size sequence
for (int gapSize = (int)(numbers.length / 2);
gapSize > 0;
gapSize = (int)(gapSize / 2.2))
{
// This should be considered an extension of the for loop's
// "update" statement.
if (gapSize == 2)
{
gapSize = 1;
}
for (int subArrayBaseIndex = 0;
subArrayBaseIndex < gapSize;
subArrayBaseIndex ++)
{
// Inside here is just insertion sort
// upperIndex is the index of the element we are "adding"
// to the sub array we are insertion sorting
for (int upperIndex = (subArrayBaseIndex + gapSize);
upperIndex < numbers.length;
upperIndex += gapSize)
{
int currentIndex = upperIndex;
while (((currentIndex - gapSize) >= 0) &&
(numbers[currentIndex] < numbers[currentIndex - gapSize]))
{
int temp = numbers[currentIndex - gapSize];
numbers[currentIndex - gapSize] = numbers[currentIndex];
numbers[currentIndex] = temp;
currentIndex -= gapSize;
}
}
}
}
if (DEBUG)
{
System.out.println("Exiting " + getSortName() +" with:");
printArray(numbers);
}
return numbers;
}
}
public class MergeSort extends Sorter
{
public String getSortName()
{
return "MergeSort";
}
public int[] sort(int[] numbers)
{
if (DEBUG)
{
System.out.println("Entering " + getSortName() + " with:");
printArray(numbers);
}
if (numbers.length <= 1)
{
return numbers;
}
// Base case
if ((numbers.length == 0) || (numbers.length) == 1)
{
return numbers;
}
int leftHalfLength = (int)(numbers.length / 2);
int[] leftHalf = new int[leftHalfLength];
int rightHalfLength = numbers.length - leftHalfLength;
int[] rightHalf = new int[rightHalfLength];
// Could also use System.arraycopy for the next two loops
for (int currentIndex = 0;
currentIndex < leftHalfLength;
currentIndex ++)
{
leftHalf[currentIndex] = numbers[currentIndex];
}
for (int currentIndex = 0;
currentIndex < rightHalfLength;
currentIndex ++)
{
rightHalf[currentIndex] = numbers[leftHalfLength + currentIndex];
}
int[] sortedLeftHalf = sort(leftHalf);
int[] sortedRightHalf = sort(rightHalf);
int currentLeftHalfIndex = 0;
int currentRightHalfIndex = 0;
for (int currentNumbersIndex = 0;
currentNumbersIndex < numbers.length;
currentNumbersIndex ++)
{
if (currentLeftHalfIndex < leftHalfLength)
{
if (currentRightHalfIndex < rightHalfLength)
{
if (sortedLeftHalf[currentLeftHalfIndex] <
sortedRightHalf[currentRightHalfIndex])
{
numbers[currentNumbersIndex] =
sortedLeftHalf[currentLeftHalfIndex];
currentLeftHalfIndex ++;
}
else
{
numbers[currentNumbersIndex] =
sortedRightHalf[currentRightHalfIndex];
currentRightHalfIndex ++;
}
}
// currentRightHalfIndex >= rightHalfLength
// We must take from the left half (There are no more
// numbers left on the right half).
else
{
numbers[currentNumbersIndex] =
sortedLeftHalf[currentLeftHalfIndex];
currentLeftHalfIndex ++;
}
}
// currentLeftHalfIndex >= leftHalfLength
// We must take from the right half (There are no more
// numbers left on the left half)
else
{
numbers[currentNumbersIndex] =
sortedRightHalf[currentRightHalfIndex];
currentRightHalfIndex ++;
}
}
if (DEBUG)
{
System.out.println("Exiting " + getSortName() + " with:");
printArray(numbers);
}
return numbers;
}
}
It is your job (in proj2) to implement this. Have Fun! I will provide my implementation after you have turned the project in.
Return to the Section 101 Homepage.