Select a Chapter: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Back to the Main Page | ||
Chapter Thirteen listings: 4 classes |
public class CompOp // collecting various sorting algorithms { // SELECTION SORT /** Precondition: size <= item.length; item[0]...item[size-1] * are non-null values all Comparable to each other. * Postcondition: The array contains the values it initially * had but with item[0]...item[size-1] in ascending order. */ public static void selectionSort (Comparable[] item, int size) { for (int k = 0; k < size - 1; k++) swapMinToFront (item, k, size - 1); } //======================= private static void swapMinToFront (Comparable[] item, int start, int end) { int indexSmallest = start; for (int k = start + 1; k <= end; k++) { if (item[k].compareTo (item[indexSmallest]) < 0) indexSmallest = k; } Comparable saved = item[start]; item[start] = item[indexSmallest]; item[indexSmallest] = saved; } //======================= /** Return the smallest value in item[start]...item[end]. */ public static Comparable findMinimum (Comparable[ ] item, int start, int end) { Comparable smallestSoFar = item[start]; for (int k = start + 1; k <= end; k++) { if (item[k].compareTo (smallestSoFar) < 0) smallestSoFar = item[k]; } return smallestSoFar; } //======================= /** Return the median of 3000 random double values. */ public static double median() // independent { final int numToSort = 3000; Double[] item = new Double [numToSort]; for (int k = 0; k < numToSort; k++) item[k] = new Double (Math.random()); selectionSort (item, numToSort); return item[numToSort / 2].doubleValue(); } //======================= // INSERTION SORT /** Precondition: size <= item.length; item[0]...item[size-1] * are non-null values all Comparable to each other. * Postcondition: The array contains the values it initially * had but with item[0]...item[size-1] in ascending order. */ public static void insertionSort (Comparable[] item, int size) { for (int k = 1; k < size; k++) insertInOrder (item, k); } //======================= private static void insertInOrder (Comparable[] item, int m) { Comparable save = item[m]; for (; m > 0 && item[m - 1].compareTo (save) > 0; m--) item[m] = item[m - 1]; item[m] = save; } //======================= // BINARY SEARCH /** Precondition: item[0]...item[size-1] are all non-null, * in ascending order, and Comparable with target. * Returns: whether target is one of the array values. */ public static boolean binarySearch (Comparable[] item, int size, Comparable target) { if (size <= 0) //1 return false; //2 int lowerBound = 0; //3 int upperBound = size - 1; //4 while (lowerBound < upperBound) //5 { int midPoint = (lowerBound + upperBound) / 2; //6 if (item[midPoint].compareTo (target) < 0) //7 lowerBound = midPoint + 1; //8 else //9 upperBound = midPoint; //10 } //11 return item[lowerBound].equals (target); //12 } //======================= // 3 RECURSIVE METHODS public static void insertionSort (Comparable[] item, int size) { if (size > 1) { insertionSort (item, size - 1); //recur insertInOrder (item, size - 1); } } //======================= public static void selectionSort (Comparable[] item, int size) { if (size > 1) { swapMaxToRear (item, 0, size - 1); selectionSort (item, size - 1); //recur } } //======================= public static void printBinary (String prefix, int numDigits) { if (numDigits <= 1) System.out.println (prefix + "0\n" + prefix + "1"); else { printBinary (prefix + "0", numDigits - 1); //recur printBinary (prefix + "1", numDigits - 1); //recur } } //======================= // QUICKSORT AND MERGESORT: MAIN METHODS /** Precondition: size <= item.length; item[0]...item[size-1] * are non-null values all Comparable to each other. * Postcondition: The array contains the values it initially * had but with item[0]...item[size-1] in ascending order. */ public static void quickSort (Comparable[] item, int size) { new QuickSorter (item).sort (0, size - 1); } //======================= /** Precondition: size <= item.length; item[0]...item[size-1] * are non-null values all Comparable to each other. * Postcondition: The array contains the values it initially * had but with item[0]...item[size-1] in ascending order. */ public static void mergeSort (Comparable[] item, int size) { Comparable[] spare = new Comparable [item.length]; new MergeSorter (item, spare).sort (0, size - 1); } //======================= // IN-PLACE MERGESORT BY 2S /** Precondition: size <= item.length; item[0]...item[size-1] * are non-null values all Comparable to each other. * Postcondition: The array contains the values it initially * had but with item[0]...item[size-1] in ascending order. */ public static void mergeSortBy2s (Comparable[] item, int size) { int jump = 1; while (jump * 2 < size) jump *= 2; for ( ; jump >= 1; jump /= 2) sortGroups (item, size, jump); } //======================= private static void sortGroups(Comparable[] item, int size, int jump) { for (int k = jump; k < size; k++) insertInOrder (item, k, jump); // left as an exercise } //======================= } // END OF CompOp
public class QuickSorter { private Comparable[] itsItem; // the array to be sorted public QuickSorter (Comparable[] item) { itsItem = item; } //======================= /** Precondition: start <= end; itsItem[start]...itsItem[end] * are the Comparable values to be sorted. */ public void sort (int start, int end) { if (start < end) //1 { int mid = split (start, end); //2 sort (start, mid - 1); //3 sort (mid + 1, end); //4 } //5 } //======================= private int split (int lo, int hi) { Comparable pivot = itsItem[lo]; //6 boolean lookHigh = true; //7 while (lo < hi) //8 { if (lookHigh) //9 { if (itsItem[hi].compareTo (pivot) >= 0) //10 hi--; //11 else //12 { itsItem[lo++] = itsItem[hi]; //13 lookHigh = false; //14 } //15 } //16 else //17 { if (itsItem[lo].compareTo (pivot) <= 0) //18 lo++; //19 else //20 { itsItem[hi--] = itsItem[lo]; //21 lookHigh = true; //22 } //23 } //24 } //25 itsItem[lo] = pivot; //26 return lo; //27 } //======================= }
public class MergeSorter { private Comparable[] itsItem; // the array to be sorted private Comparable[] itsSpare; // spare to facilitate sorting public MergeSorter (Comparable[] item, Comparable[] spare) { itsItem = item; itsSpare = spare; } //======================= public void sort (int start, int end) { if (start < end) //1 { int mid = (start + end) / 2; //2 sortToSpare (start, mid); //3 sortToSpare (mid + 1, end); //4 merge(itsSpare, itsItem, start, mid, mid + 1, end); //5 } //6 } //======================= private void sortToSpare (int start, int end) { if (start >= end) //7 itsSpare[start] = itsItem[start]; //8 else //9 { int mid = (start + end) / 2; //10 sort (start, mid); //11 sort (mid + 1, end); //12 merge(itsItem, itsSpare, start, mid, mid + 1, end); //13 } //14 } //======================= private void merge (Comparable[] from, Comparable[] into, int lo, int mid, int hi, int end) { for (int spot = lo; spot <= end; spot++) //15 { if (lo > mid || (hi <= end //16 && from[lo].compareTo (from[hi]) > 0)) //17 into[spot] = from[hi++]; //18 else //19 into[spot] = from[lo++]; //20 } //21 } //======================= }
class WorkerByBirth implements Comparable { private static int theNumComps = 0; private Object itsWorker; public WorkerByBirth (Object given) { itsWorker = given; } //======================= public int compareTo (Object ob) { theNumComps++; return ((Worker) itsWorker).getBirthYear() - ((Worker) ob).getBirthYear(); } //======================= public static int numComps (Object[] givenArray, int size) { Comparable[] tempArray = new Comparable [size]; for (int k = 0; k < size; k++) tempArray[k] = new WorkerByBirth (given[k]); theNumComps = 0; CompOp.insertionSort (tempArray, size); for (int k = 0; k < size; k++) given[k] = tempArray[k].itsWorker; return theNumComps; } //======================= } |
Layout and Design Copyright © Psumonix, LLC. All Rights Reserved. |