COP 3337 Section U08 Fall 2015 SORTING METHODS: BUBBLE SORT, MERGE SORT, QUICK SORT ==================================================== Thers are 7 java files: 1. ArrayUtil, that generates a random array 2. BubbleSorter, that implements bubble sort 3. Main method that does the comparison 4. MergeSorter implements merge sort 5. QuickSorter that uses quick sort 6. StopWatch that implements the clock 7. The output The files: 1. The ArrayUtil.java file import java.util.Random; /** This class contains methods for array manipulation * */ public class ArrayUtil { // generate a random array of size length with numbers // between 0 and n-1 public static int[] randomIntArray(int length,int n) { int[] a = new int[length]; Random generator = new Random(); for (int i = 0; i < a.length; i++) a[i] = generator.nextInt(n); return a; } // print the array public static void print(int[] a) { for (int i = 0; i < a.length; i++) System.out.print(a[i] + " "); System.out.println(); } } ------------------------------------------------------------------------- 2. The BubbleSorter class // this class sorts using bubble sort public class BubbleSorter { // the field private int[] a; // the constructor public BubbleSorter(int[] anArray) { a = anArray; } /** Sorts the array managed by this merge sorter */ public void sort() { // initialize the position to be filled int pos = a.length - 1; // sorted is set to true when the sweep found // no out of order pairs boolean sorted = false; while (!sorted) { // fill position pos sorted = true; // compair the pairs a[i] and a[i+1] // swap them if they are out of order for (int i = 0; i < pos; i++) if (a[i] > a[i+1] ) { // swap them int temp = a[i]; a[i] = a[i+1]; a[i+1] = temp; sorted = false; // we found an out of order pair } // decrese pos pos--; } // end while } // end sort } ------------------------------------------------------------------------- 3. The Main class /* tests the merge sort algorithm */ public class Main { public static void main(String[] args) { // print the title System.out.println("Comparing Merge Sort, QuickSort, and Bubble Sort"); System.out.println("=================================================\n\n\n"); // generate a random array with ARRAY_SIZE integers final int ARRAY_SIZE = 200000; final int NUMBER_SIZE = 1000000000; System.out.println("We generate a random array with " + ARRAY_SIZE + " integers."); System.out.println("We sort it by using the merge sort, bubble sort, and quicksort " + "and compare the times."); // get a random array int[] sample = ArrayUtil.randomIntArray(ARRAY_SIZE, NUMBER_SIZE); int[] a = (int[]) sample.clone(); // set a timer for merge sort and sort the array StopWatch timer = new StopWatch(); timer.start(); MergeSorter mergeSorter = new MergeSorter(a); mergeSorter.sort(); // stop the timer timer.stop(); System.out.println("Elapsed time for merge sorter = " + timer.getElapsedTime() + " milliseconds."); // do the same thing for bubble sort a = (int[]) sample.clone(); // set a timer StopWatch timer2 = new StopWatch(); timer2.start(); BubbleSorter bubbleSorter = new BubbleSorter(a); bubbleSorter.sort(); // stop the timer timer2.stop(); System.out.println("Elapsed time for bubble sorter = " + timer2.getElapsedTime() + " milliseconds."); // do the same thing for quicksort sort the array // and print the sorted array a = (int[]) sample.clone(); // set a timer StopWatch timer3 = new StopWatch(); timer3.start(); QuickSorter.sort(a); // stop the timer timer3.stop(); System.out.println("Elapsed time for quicksort = " + timer3.getElapsedTime() + " milliseconds."); } } ------------------------------------------------------------------------- 4. The MergeSorter class /* This class sorts an array using the merge sort algorithm */ public class MergeSorter { /* constructs a merge sorter. * @param anArray is the array to be sorted */ public MergeSorter(int[] anArray) { a = anArray; } /** Sorts the array managed by this merge sorter */ public void sort() { if (a.length <= 1) return; // split the array in two halves int[] first = new int[a.length /2]; int[] second = new int[a.length - first.length]; /* copy a into these two halves */ System.arraycopy(a,0,first,0,first.length); System.arraycopy(a,first.length,second,0,second.length); /* sort the two halves */ MergeSorter firstSorter = new MergeSorter(first); MergeSorter secondSorter = new MergeSorter(second); firstSorter.sort(); // recursive call secondSorter.sort(); // recursive call // merge the two sorted halves merge(first,second); } /** Merges two sorted arrays. * @param first is the first array * @param second is the second array */ private void merge(int[] first, int[] second) { // merge the two halves into a temporary array int iFirst = 0; // the candidate in the first array int iSecond = 0; // the candidate in the second array int j = 0; // the position to be filled // as long as iFirst and iSecond are valid enter the // smallest while (iFirst < first.length && iSecond < second.length) { if (first[iFirst] < second[iSecond]) { a[j] = first[iFirst]; iFirst++; } else { a[j] = second[iSecond]; iSecond++; } j++; } // copy the rest of the two arrays // only one call is executed System.arraycopy(first,iFirst,a,j,first.length - iFirst); System.arraycopy(second, iSecond,a,j,second.length - iSecond); } // end merge // the field private int[] a; } ------------------------------------------------------------------------- 5. The QuickSorter class public class QuickSorter { // sort public static void sort(int[] a) { if (a != null ) quickSort(a, 0,a.length -1); } // sort the slice a[low:high] public static void quickSort(int a[], int low, int high) { // handle the cases when the slice has <= 3 items if (high - low <= 0) return; if ( high - low == 1) { // sort 2 if (a[low] > a[high]) swap(a,low,high); return; } if (high - low == 2) { // sort 3 if (a[low] > a[low +1]) swap(a,low,low +1); if (a[low+1] > a[low +2]) swap(a,low + 1,low + 2); if (a[low] > a[low + 1]) swap(a,low,low +1); return; } // sort when a.length >= 4 // sort a[low],a[mid], a[high] int mid = (low+high) / 2; if (a[mid] < a[low]) swap(a,mid,low); if (a[high] < a[mid]) swap(a, high,mid); if (a[mid] < a[low]) swap(a, mid, low); // move the pivot at position high -1 swap(a, mid,high -1); int pivot = a[high - 1]; // begin partitioning int i,j; for (i = low, j=high -1;;) { while (a[++i] < pivot); // advance i while (a[--j] > pivot); // decrease j if (i >= j) break; swap(a,i,j); } // restore pivot swap(a,i,high-1); // recurse quickSort(a,low,i-1); quickSort(a,i+1,high); } // swap the contents of a[i] and a[j] public static void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } } ------------------------------------------------------------------------- 6. The StopWatch class /** A stopwatch accumulates time while it is running. You can * repeatedly start and stop the stopwatch. */ public class StopWatch { /* Constructs a stopwatch that is in the stopped state * and has no time accumulated. */ public StopWatch() { reset(); } /* Starts the stopWatch */ public void start() { if (isRunning) return; isRunning = true; startTime = System.currentTimeMillis(); } /* Stops the stopwatch */ public void stop() { if (!isRunning) return; isRunning = false; long endTime = System.currentTimeMillis(); elapsedTime = elapsedTime + endTime - startTime; } /* @return the total elapsed time */ public long getElapsedTime() { if (isRunning) { long endTime = System.currentTimeMillis(); elapsedTime = elapsedTime + endTime - startTime; startTime = endTime; } return elapsedTime; } /* Stops the watch and resets the elapsed time to 0. */ public void reset() { elapsedTime = 0; isRunning = false; } private long elapsedTime; private long startTime; private boolean isRunning; } ------------------------------------------------------------------------- 7. The output: run: Comparing Merge Sort, QuickSort, and Bubble Sort ================================================= We generate a random array with 200000 integers. We sort it by using the merge sort, bubble sort, and quicksort and compare the times. Elapsed time for merge sorter = 120 milliseconds. Elapsed time for bubble sorter = 104600 milliseconds. Elapsed time for quicksort = 100 milliseconds. BUILD SUCCESSFUL (total time: 1 minute 47 seconds)