/* * This is a summary of sorting routines that make the AP * folks happy. Note that there is generally more * than one way to write each of these, so if you * like your way of writing one of them better than * what you see here, that's fine. * * I suggest that you use this code to understand the * mechanics of how each sort works. To keep it simple, * try tracing each sort by hand on each of the following * arrays: * * { 3, 6, 1, 5, 2, 4 } * { 6, 5, 4, 3, 2, 1 } * * Try to keep track of the number of comparisons done * between elements in the array and the number of times * elements are swapped. (Treat temp = a, a = b, b = temp * as one swap for simplicity.) * * For heapsort and mergesort, you may wish to try a * somewhat larger set of data, say: * * { 7, 12, 9, 2, 3, 11, 1, 8, 6, 10, 5, 4 } * * I have intentionally left no documentation. * I'd like you to be able to explain to me what happens * when this code executes in terms of how the state of * the array is altered as it goes from being unsorted to sorted. * Also be able to explain the order of growth as the number * of elements, n, gets larger. It's easy enough to simply * state that bubble sort is O(n^{2}), but I want to hear * your rationale for why. */ // QUICK SORT void quicksort(int[] a) { quick(a, 0, a.length-1); } void quick(int[] a, int left, int right) { if (right > left) { int pivotPos = partition(a, left, right); quick(a, left, pivotPos-1); quick(a, pivotPos+1, right); } } int partition(int[] a, int left, int right) { int splitPos = left; for (int i = left; i < right; i++) { if (a[i] < a[right]) { swap(a, i, splitPos); splitPos++; } } swap(a,splitPos,right); return splitPos; } void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } // MERGE SORT // Algorithm taken from H.W. Lang, FH Flensburg // (http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/merge/mergen.htm) public static void mergesort(int[] arr) { ms(arr, 0, arr.length-1); } private static void ms(int[] a, int low, int high) { if (low < high) { int mid = (low + high) / 2; ms(a, low, mid); ms(a, mid+1, high); merge(a, low, mid, high); } } private static void merge (int[] a, int low, int mid, int high) { int[] b = new int[a.length]; int i, j, k; for (i = low; i <= high; i++) b[i]=a[i]; i = low; j = mid+1; k = low; while (i <= mid && j <= high) if (b[i]<=b[j]) a[k++]=b[i++]; else a[k++]=b[j++]; while (i <= mid) a[k++]=b[i++]; } // BUBBLE SORT void bubbleSort(int[] a) { for (int i = 0; i < a.length; i++) { for (int j = 0; j < a.length - i - 1; j++) { if (a[j] > a[j+1]) { swap(a, j, j+1); } } } } // INSERTION SORT void insertionSort(int[] a) { for (int i = 0; i < a.length; i++) { insert(a, i); } } void insert(int[] a, int i) { int j; for (j = 0; a[i] > a[j] && j < i; j++) {} int temp = a[i]; for (int k = i; k > j; k--) { a[k] = a[k-1]; } a[j] = temp; } // SELECTION SORT void selectionSort(int[] a) { int min, minPos; for (int i = 0; i < a.length; i++) { min = a[i]; minPos = i; for (int j = i; j < a.length; j++) { if (a[j] < min) { min = a[j]; minPos = j; } } swap(a, i, minPos); } } // HEAP SORT // Note the use of modular, top-down programming // We know that heapsort needs to build a heap and then sort it, // so why not write that as code and then fill in the needed methods? public static void heapsort(int[]a) { buildHeap(a); sortHeap(a); } // I let the other methods be private to make a point about public. // The only method that should be visible if you want to do heapsort // is the heapsort method itself. Unless you have a reason to let // a method like buildheap be visible outside this class, it probably // should be private. That said, the AP graders are expecting public // methods and private instance variables; on the actual test, use // public everywhere for methods unless instructed otherwise. // Trickle hasn't been written, but building the heap is the process // of going through the array, right to left, and performing trickle // at each place. private static void buildHeap(int[] a) { for (int i = a.length-1; i >= 0; i--) { trickle(a, i, a.length); } } // Swap the root with the last unsorted position // Then trickle the new root to maintain a heap private static void sortHeap(int[] a) { for (int i = a.length-1; i >= 0; i--) { swap(a, 0, i); trickle(a, 0, i); } } // The game plan: // * If a node has no children, done // * If a node has one child, check to see if a swap is needed // * If a node has two children, check to see which is bigger and if a swap is needed private static void trickle(int[] a, int i, int lastPosition) { // max contains the bigger child datum // maxPos contains the place in the array where the bigger child datum is contained int max = 0, maxPos = 0; if (hasChildren(i, lastPosition)) { if (hasOnlyLeftChild(i, lastPosition)) { max = a[left(i)]; maxPos = left(i); } else { maxPos = (a[left(i)] > a[right(i)]) ? left(i) : right(i); max = a[maxPos]; } // Now determine if a swap is warranted // Note that lastPosition holds the biggest array index into which // a datum can be trickled. We don't want to trickle into something // that is already sorted! if (max > a[i]) { swap(a, i, maxPos); trickle(a, maxPos, lastPosition); } } } // A slew of helper functions to get the details done // Sometimes it is easier to identify some of these and write them // before writing the higher-level stuff. Deciding what to write // first can be an art form. private static int left(int x) { return 2*x + 1; } private static int right(int x) { return 2*x + 2; } private static int parent(int x) { return (x-1) / 2; } private static void swap(int[] arr, int i1, int i2) { int temp = arr[i1]; arr[i1] = arr[i2]; arr[i2] = temp; } private static boolean hasChildren(int index, int length) { // Imagine a binary number. Shifting all of the 1s to the right // by a position is the same thing as dividing by two. It also // behaves as integer arithmetics as if there is a one in the // rightmost position, it gets shifted out of existence. // No critical reason to do it this way, just wanted to show it. return (index+1 <= (length >> 1)); } private static boolean hasOnlyLeftChild(int index, int length) { return ((index*2)+2 == length); } // Pretty printing procedure for arrays of integers void printArray(int[] a) { System.out.print("{ " + a[0]); for (int i = 1; i < a.length; i++) { System.out.print(", " + a[i]); } System.out.println(" }"); }