/* Peter Huitsing Lab 11&12 April 3, 2003 Instructor - Dr. Wainright */ import java.util.Random; import java.util.Vector; public class SortTestDrive { public static void main(String [] args) { final int[] setSize = {100, 1000, 10000, 65536, 131072}; //set up data vector Object[][][] data = new Object[5][5][5]; //sets up data array Random random = new Random(System.currentTimeMillis()); //random number generator, seed w/ system timer long start, finish; //stuff for cpu timer Double cputime; //main running loop for (int selectSetSize = 0; selectSetSize < setSize.length-2; selectSetSize++) {//iterate through the set sizes //System.out.println("selectSetSize> " + selectSetSize); for (int randomSetNumber = 0; randomSetNumber < 5; randomSetNumber++) { //iterate through the 5 random sets //System.out.println("randomSetNumber> " + randomSetNumber); Integer[] randomSet = new Integer[setSize[selectSetSize]]; //create random array for (int i = 0; i < setSize[selectSetSize]; i++) {//fill up the array w/ random stuff randomSet[i] = new Integer(random.nextInt(29999)+1); //System.out.println("setSize> " + randomSet[i]); } /* BubbleSort = 0 insertionSort = 1 selectionSort = 2 mergeSort = 3 quickSort = 4 */ System.out.println("Set size: " + setSize[selectSetSize]); //BubbleSort Integer[] sortSet = (Integer[])randomSet.clone(); start = System.currentTimeMillis(); bubbleSort(sortSet, sortSet.length); finish = System.currentTimeMillis(); cputime = new Double((finish - start) / 1000.0); //cpu time in seconds System.out.println("Bubble Sort: " + cputime); data[selectSetSize][0][randomSetNumber]=cputime; //insertionSort sortSet = (Integer[])randomSet.clone(); start = System.currentTimeMillis(); insertionSort(sortSet, sortSet.length); finish = System.currentTimeMillis(); cputime = new Double((finish - start) / 1000.0); //cpu time in seconds System.out.println("Insertion Sort: " + cputime); data[selectSetSize][1][randomSetNumber]=cputime; //selectionSort sortSet = (Integer[])randomSet.clone(); start = System.currentTimeMillis(); selectionSort(sortSet, sortSet.length); finish = System.currentTimeMillis(); cputime = new Double((finish - start) / 1000.0); //cpu time in seconds System.out.println("Selection Sort: " + cputime); data[selectSetSize][2][randomSetNumber]=cputime; //mergeSort sortSet = (Integer[])randomSet.clone(); start = System.currentTimeMillis(); mergeSort(sortSet, 0, sortSet.length-1); finish = System.currentTimeMillis(); cputime = new Double((finish - start) / 1000.0); //cpu time in seconds System.out.println("Merge Sort: " + cputime); data[selectSetSize][3][randomSetNumber]=cputime; //quickSort sortSet = (Integer[])randomSet.clone(); start = System.currentTimeMillis(); quickSort(sortSet, 0, sortSet.length-1); finish = System.currentTimeMillis(); cputime = new Double((finish - start) / 1000.0); //cpu time in seconds System.out.println("Quick Sort: " + cputime); data[selectSetSize][4][randomSetNumber]=cputime; //for (int i = 0; i < sortSet.length; i++) System.out.println(sortSet[i]); System.out.println("-----------------------------------------\n\n"); } } } //end main //static methods (namely, the sorting methods) public static void bubbleSort(Comparable[] theArray, int n) { // --------------------------------------------------- // Sorts the items in an array into ascending order. // Precondition: theArray is an array of n items. // Postcondition: theArray is sorted into ascending // order. // --------------------------------------------------- boolean sorted = false; // false when swaps occur for (int pass = 1; (pass < n) && !sorted; ++pass) { // Invariant: theArray[n+1-pass..n-1] is sorted // and > theArray[0..n-pass] sorted = true; // assume sorted for (int index = 0; index < n-pass; ++index) { // Invariant: theArray[0..index-1] <= theArray[index] int nextIndex = index + 1; if (theArray[index].compareTo(theArray[nextIndex]) > 0) { // exchange items Comparable temp = theArray[index]; theArray[index] = theArray[nextIndex]; theArray[nextIndex] = temp; sorted = false; // signal exchange } // end if } // end for // Assertion: theArray[0..n-pass-1] < theArray[n-pass] } // end for } // end bubbleSort //---------------------------------------------------------------- public static void insertionSort(Comparable[] theArray, int n) { // --------------------------------------------------- // Sorts the items in an array into ascending order. // Precondition: theArray is an array of n items. // Postcondition: theArray is sorted into ascending // order. // --------------------------------------------------- // unsorted = first index of the unsorted region, // loc = index of insertion in the sorted region, // nextItem = next item in the unsorted region // initially, sorted region is theArray[0], // unsorted region is theArray[1..n-1]; for (int unsorted = 1; unsorted < n; ++unsorted) { // Invariant: theArray[0..unsorted-1] is sorted // find the right position (loc) in // theArray[0..unsorted] for theArray[unsorted], // which is the first item in the unsorted // region; shift, if necessary, to make room Comparable nextItem = theArray[unsorted]; int loc = unsorted; while ((loc > 0) && (theArray[loc-1].compareTo(nextItem) > 0)) { // shift theArray[loc-1] to the right // BUG FIX: replaced the following line with the two that follows it // theArray[loc--] = theArray[loc-1]; theArray[loc] = theArray[loc-1]; loc--; } // end while // insert nextItem into sorted region theArray[loc] = nextItem; } // end for } // end insertionSort public static void selectionSort(Comparable[] theArray, int n) { // --------------------------------------------------- // Sorts the items in an array into ascending order. // Precondition: theArray is an array of n items. // Postcondition: theArray is sorted into // ascending order. // Calls: indexOfLargest. // --------------------------------------------------- // last = index of the last item in the subarray of // items yet to be sorted // largest = index of the largest item found for (int last = n-1; last >= 1; last--) { // Invariant: theArray[last+1..n-1] is sorted // and > theArray[0..last] // select largest item in theArray[0..last] int largest = indexOfLargest(theArray, last+1); // swap largest item theArray[largest] with // theArray[last] Comparable temp = theArray[largest]; theArray[largest] = theArray[last]; theArray[last] = temp; } // end for } // end selectionSort //----------------------------------------------------------- private static int indexOfLargest(Comparable[] theArray, int size) { // --------------------------------------------------- // Finds the largest item in an array. // Precondition: theArray is an array of size items; // size >= 1. // Postcondition: Returns the index of the largest // item in the array. // --------------------------------------------------- int indexSoFar = 0; // index of largest item found so far // Invariant: theArray[indexSoFar]>=theArray[0..currIndex-1] for (int currIndex = 1; currIndex < size; ++currIndex) { if (theArray[currIndex].compareTo(theArray[indexSoFar])>0) { indexSoFar = currIndex; } // end if } // end for return indexSoFar; // index of largest item } // end indexOfLargest //----------------------------------------------------------- public static void mergeSort(Comparable[] theArray, int first, int last) { // --------------------------------------------------------- // Sorts the items in an array into ascending order. // Precondition: theArray[first..last] is an array. // Postcondition: theArray[first..last] is sorted in // ascending order. // Calls: merge. // --------------------------------------------------------- if (first < last) { // sort each half int mid = (first + last)/2; // index of midpoint // sort left half theArray[first..mid] mergeSort(theArray, first, mid); // sort right half theArray[mid+1..last] mergeSort(theArray, mid+1, last); // merge the two halves merge(theArray, first, mid, last); } // end if } // end mergesort private static void merge(Comparable[] theArray, int first, int mid, int last) { // --------------------------------------------------------- // Merges two sorted array segments theArray[first..mid] and // theArray[mid+1..last] into one sorted array. // Precondition: first <= mid <= last. The subarrays // theArray[first..mid] and theArray[mid+1..last] are // each sorted in increasing order. // Postcondition: theArray[first..last] is sorted. // Implementation note: This method merges the two // subarrays into a temporary array and copies the result // into the original array anArray. // --------------------------------------------------------- int maxSize = theArray.length; // temporary array Comparable[] tempArray = new Comparable[maxSize]; // initialize the local indexes to indicate the subarrays int first1 = first; // beginning of first subarray int last1 = mid; // end of first subarray int first2 = mid + 1; // beginning of second subarray int last2 = last; // end of second subarray // while both subarrays are not empty, copy the // smaller item into the temporary array int index = first1; // next available location in // tempArray while ((first1 <= last1) && (first2 <= last2)) { // Invariant: tempArray[first1..index-1] is in order if (theArray[first1].compareTo(theArray[first2])<0) { tempArray[index] = theArray[first1]; first1++; } else { tempArray[index] = theArray[first2]; first2++; } // end if index++; } // end while // finish off the nonempty subarray // finish off the first subarray, if necessary while (first1 <= last1) { // Invariant: tempArray[first1..index-1] is in order tempArray[index] = theArray[first1]; first1++; index++; } // end while // finish off the second subarray, if necessary while (first2 <= last2) { // Invariant: tempArray[first1..index-1] is in order tempArray[index] = theArray[first2]; first2++; index++; } // end while // copy the result back into the original array for (index = first; index <= last; ++index) { theArray[index] = tempArray[index]; } // end for } // end merge //----------------------------------------------------------- public static void quickSort(Comparable[] theArray, int first, int last) { // --------------------------------------------------------- // Sorts the items in an array into ascending order. // Precondition: theArray[first..last] is an array. // Postcondition: theArray[first..last] is sorted. // Calls: partition. // --------------------------------------------------------- int pivotIndex; if (first < last) { // create the partition: S1, Pivot, S2 pivotIndex = partition(theArray, first, last); // sort regions S1 and S2 quickSort(theArray, first, pivotIndex-1); quickSort(theArray, pivotIndex+1, last); } // end if } // end quickSort private static int partition(Comparable[] theArray, int first, int last) { // --------------------------------------------------------- // Partitions an array for quicksort. // Precondition: theArray[first..last] is an array; // first <= last. // Postcondition: Returns the index of the pivot element of // theArray[first..last]. Upon completion of the method, // this will be the index value lastS1 such that // S1 = theArray[first..lastS1-1] < pivot // theArray[lastS1] == pivot // S2 = theArray[lastS1+1..last] >= pivot // Calls: choosePivot. // --------------------------------------------------------- // tempItem is used to swap elements in the array Comparable tempItem; // place pivot in theArray[first] choosePivot(theArray, first, last); Comparable pivot = theArray[first]; // reference pivot // initially, everything but pivot is in unknown int lastS1 = first; // index of last item in S1 // move one item at a time until unknown region is empty for (int firstUnknown = first + 1; firstUnknown <= last; ++firstUnknown) { // Invariant: theArray[first+1..lastS1] < pivot // theArray[lastS1+1..firstUnknown-1] >= pivot // move item from unknown to proper region if (theArray[firstUnknown].compareTo(pivot) < 0) { // item from unknown belongs in S1 ++lastS1; tempItem = theArray[firstUnknown]; theArray[firstUnknown] = theArray[lastS1]; theArray[lastS1] = tempItem; } // end if // else item from unknown belongs in S2 } // end for // place pivot in proper position and mark its location tempItem = theArray[first]; theArray[first] = theArray[lastS1]; theArray[lastS1] = tempItem; return lastS1; } // end partition private static void choosePivot(Comparable[] theArray, int first, int last) { // --------------------------------------------------------- // Chooses a pivot for quicksort's partition algorithm and // swaps it with the first item in an array. // Precondition: theArray[first..last] is an array; // first <= last. // Postcondition: theArray[first] is the pivot. // --------------------------------------------------------- // Implementation left as an exercise. //use first one. haha } // end choosePivot } // end class