Sorting

1. Download the following files to your week11 package folder 1. AbstractSort.java 2. HeapSort.java 3. TestCaseSorting.java

2. Create the classes BubbleSort.java and SelectionSort.java 1. Reference the provided UML and the JavaDoc for the proper class definitions 2. Note that each class extends AbstractSort; use the HeapSort as a reference

3. Implement the each sorting algorithm in the appropriate class. Note: the details for the sorting algorithms are available in the text and the supplied JavaDoc.

4. TestHarness.java combines all the tests into a single test: TestHarness.java

AbstractSort.java package week11; /** * Base class for sorting routines * * @author scottl * */ public abstract class AbstractSort { /** * Constructor * * @param name * Name of the sort routine */ public AbstractSort(String name, int[] list) { m_sortName = name; m_list = list; } /** * Sorts the data */ public abstract void sort(); /** * The sort routine name * * @return Name of the sort routine */ public String getName() { return m_sortName; } public int[] getList() { return m_list; } /** The name of the sort routine */ private String m_sortName; protected int[] m_list; } HeapSort.java package week11; /** * HeapSort uses a special data structure called a heap. * A heap is a type of tree with some specific characteristics defined. * The top most node is called the root node of a heap. * Nodes in a heap are indexed 0,1,2,3, and so on in the top-to-bottom, left-to-right order, starting from the root * * 0 * / \ * 1 2 * / \ / \ * 3 4 5 6 * * A node can have zero, one or two children. * The constraints a heap must satisfy are: *

*

Structure constraint: Nodes in a heap must follow the index order. See page 647 in text for examples of non-heaps

*

Value relationship constraint: A value stored in a node MUST be larger than the max value of its left and right children.

*

* * HeapSort is implemented in two phases: *

*

Construction phase: Construct a heap given N elements

*

Extraction phase: Pull out the value in the root successively, creating a new heap with one less element after each extraction loop

*

* * The construct algorithm: * The heap is implemented in an array that represents a heap (tree) *

*

Loop through the heap starting at the heap length - 2

*

Set the current index to i and the done flag to false

*

*

Loop until done

*

See if the current node has children

*

If it has children, get the larger child else set the done flag to true

*

If the current node is smaller than the child, swap the nodes else set the done flag to true

*

*

* * The extract algorithm * The heap is implemented in an array that represents a heap (tree) *

*

Create an array to receive the sorted items

*

Loop through the heap starting at the heap length - 2

*

Remove the root node

*

Move the last node to the root

*

Rebuild the heap

*

Next pass

* * @author scottl * */ public class HeapSort extends AbstractSort { /** * Constructor * * @param list * Array of ints */ public HeapSort(int[] list) { super("HeapSort", list); } @Override public void sort() { heap = m_list; sortedList = new int[m_list.length]; construct(); // construction phase: construct the heap extract(); // extraction phase: extract root nodes m_list = sortedList; } /** * Sets the internal array to the passed data. * * @param data * an int array to be sorted */ public void setData(int[] data) { heap = new int[data.length]; sortedList = new int[data.length]; for(int i = 0; i < data.length; i++) { heap[i] = data[i]; // System.out.println( heap[i] ); //TEMP } } /** * Performs the construction phase of the heapsort. */ private void construct() { int current, maxChildIndex; boolean done; for(int i = (heap.length - 2) / 2; i >= 0; i--) { current = i; done = false; while(!done) { if(2 * current + 1 > heap.length - 1) { // current node has no children, so stop done = true; } else { // current node has at least one child, // get the index of larger child maxChildIndex = maxChild(current, heap.length - 1); if(heap[current] < heap[maxChildIndex]) { swap(current, maxChildIndex); current = maxChildIndex; } else { // value relationship constraint // is satisfied, so stop done = true; } } } assert isValidHeap(heap, i, heap.length - 1) : "Error: Construction phase is not working " + "correctly"; } // testPrint(heap.length); //TEMP } /** * Performs the extraction phase of the heapsort */ private void extract() { int current, maxChildIndex; boolean done; for(int size = heap.length - 1; size >= 0; size--) { // remove the root node data sortedList[size] = heap[0]; // move the last node to the root heap[0] = heap[size]; // rebuild current = 0; done = false; while(!done) { if(2 * current + 1 > size) { // current node has no children, so stop done = true; } else { // current node has at least one child, get the index of // larger child maxChildIndex = maxChild(current, size); if(heap[current] < heap[maxChildIndex]) { swap(current, maxChildIndex); current = maxChildIndex; } else { // value relationship constraint is satisfied, so stop done = true; } } } assert isValidHeap(heap, 0, size) : "Error: Extraction phase is not working correctly"; // testPrint( size ); //TEMP } } /** * Finds the position of the larger child of a node at position 'location'. * * @param location * the position of a node * @param end * the position of the last node in this heap * * @return the position of a larger child */ private int maxChild(int location, int end) { int result, leftChildIndex, rightChildIndex; rightChildIndex = 2 * location + 2; leftChildIndex = 2 * location + 1; // Precondition: node at 'location' has at least one child assert leftChildIndex <= end : "Error: node at position " + location + "has no children."; if(rightChildIndex <= end && heap[leftChildIndex] < heap[rightChildIndex]) { result = rightChildIndex; } else { result = leftChildIndex; } return result; } /** * Swaps the values in positions loc1 and loc2 * * @param loc1 * the position of the first int * @param loc2 * the position of the second int */ private void swap(int loc1, int loc2) { int temp; temp = heap[loc1]; heap[loc1] = heap[loc2]; heap[loc2] = temp; } /** * Verifies the valid heap. * * @param heap * the array containing the heap * @param start * the first (root) position of this heap * @param end * the last position of this heap * * @return true if it is a valid heap; otherwise false */ private boolean isValidHeap(int[] heap, int start, int end) { for(int i = start; i < end / 2; i++) { if(heap[i] < Math.max(heap[2 * i + 1], heap[2 * i + 2])) { return false; } } return true; } /** * Integer array for implementing a heap */ private int[] heap; /** * Integer array for the sorted list */ private int[] sortedList; } TestCaseSorting.java package week11; import java.util.Arrays; import java.util.Random; import test.AbstractTestCase; public class TestCaseSorting extends AbstractTestCase { public TestCaseSorting() { super("TestCaseSorting"); } @Override protected boolean runTest() { boolean success = true; int runs = 10; for(int i = 0; i < runs; i++) { success = test(); } return success; } @Override protected String results() { return m_results; } private boolean test() { boolean result = true; int[] testList = getTestList(); trace(" Processing " + testList.length + " items..."); // Make copies of the test data so we can compare them afterward // Remember, the array list gets passed by reference int[] bubbleList = Arrays.copyOf(testList, testList.length); int[] selectionList = Arrays.copyOf(testList, testList.length); int[] heapList = Arrays.copyOf(testList, testList.length); //int[] mySortList = Arrays.copyOf(testList, testList.length); //int[] quickList = Arrays.copyOf(testList, testList.length); BubbleSort bubble = new BubbleSort(bubbleList); SelectionSort selection = new SelectionSort(selectionList); HeapSort heap = new HeapSort(heapList); //MyClass mySort = new MyClass(mySortList); //QuickSort quick = new QuickSort(quickList); int[] bubbleSortedList = runTest(bubble); int[] selectionSortedList = runTest(selection); int[] heapSortedList = runTest(heap); //int[] mySortedList = runTest(mySort); // int[] quickSortedList = runTest(quick); if(!verifySorts(bubbleSortedList, selectionSortedList, heapSortedList))//, //quickSortedList)) { m_results += "Sort routines did not match "; } return result; } private boolean verifySorts(int[] a, int[] b, int[] c)//, int[] d) { boolean result = true; // verify lengths are the same if(a.length != b.length && a.length != c.length && b.length != c.length) //&& b.length != d.length) { result = false; String msg = String .format("Lengths different; bubble = %d, selection = %d, heap = %d", //d = %d", a. length, b.length, c.length);//, d[i]); //trace(msg); m_results = msg + " "; } else { for(int i = 0; i < a.length; i++) { boolean same = a[i] == b[i] && b[i] == c[i]; // using transitive if(!same) { String msg = String .format("Mismatched value at index %d; bubble = %d, selection = %d, heap = %d", //d = %d", i, a[i], b[i], c[i]);//, d[i]); //trace(msg); m_results = msg + " "; result = false; break; // early out } } } return result; } private static int[] getTestList() { Random rand = new Random(); int size = 10000; int[] list = new int[size]; for(int i = 0; i < size; i++) { int val = rand.nextInt(size); list[i] = val; } return list; } private int[] runTest(AbstractSort sorter) { trace("Testing sort routine " + sorter.getName()); trace("---------------------------------"); long start = System.nanoTime(); sorter.sort(); long end = System.nanoTime(); long elapsed = end - start; trace(String.format("Processed in: %d ", elapsed)); trace("================================="); return sorter.getList(); } private String m_results = ""; } TestHarness.java package week11; import test.TestEngine; public class TestHarness { public static void main(String[] args) { trace("Starting test..."); trace(" -- setup test data"); TestEngine engine = new TestEngine(); engine.addTest(new TestCaseBinarySearch()); engine.addTest(new TestCaseLinearSearch()); engine.addTest(new TestCaseSorting()); engine.runTests(); trace("Completed test"); System.exit(0); } static private void trace(String msg) { System.out.println(msg); } }