*Implementations of three classic sorting algorithms: Quicksort, Bubble sort, and Selection sort. *Use code from RecoursiveFibonacciTimer (below) to measure time it took each of three classic sorting algorithms (below): Quicksort (example below), Bubblesort (example below), and Selectionsort (example below). * In main() write code that creates 3 identical arrays of size 1000000 filled with random numbers in the range [1 1000000] *Use code to measure time it took each of the sorting algorithms to sort the array. Each sorting method must have the same set of numbers to sort, so use one of the 3 arrays you created for each method. *When printing out time, convert it into minutes and seconds format. *In the beginning of your file with the solution, in comments, record the timing results you got when running the sorting methods for me to see. *Finally, find out how much time it takes Quicksort to sort 100000000 random integers on your computer. Record that result in the beginning of the source code file too. Name your solution EmpiricalStudy.java

/****************************** 1. Example of Quicksort code ******************************/ public class QuickSort { public static void quickSort(int array[]) { doQuickSort(array, 0, array.length - 1); }

private static void doQuickSort(int array[], int start, int end) { int pivotPoint; if (start < end) { pivotPoint = partition(array, start, end); doQuickSort(array, start, pivotPoint - 1); doQuickSort(array, pivotPoint + 1, end); } } private static int partition(int array[], int start, int end) { int pivotValue; // To hold the pivot value int endOfLeftList; // Last element in the left sub list. int mid; // To hold the mid-point subscript mid = (start + end) / 2; swap(array, start, mid); pivotValue = array[start]; endOfLeftList = start; for (int scan = start + 1; scan <= end; scan++) { if (array[scan] < pivotValue) { endOfLeftList++; swap(array, endOfLeftList, scan); } } swap(array, start, endOfLeftList); return endOfLeftList; }

private static void swap(int[] array, int a, int b) { int temp; temp = array[a]; array[a] = array[b]; array[b] = temp; } }

/****************************** 2. Example of Bubblesort code ******************************/ public class BubbleSort { public static void bubbleSort(int[] array) { int lastPos; // Position of last element to compare int index; // Index of an element to compare int temp; // Used to swap to elements for (lastPos = array.length - 1; lastPos >= 0; lastPos--) { for (index = 0; index <= lastPos - 1; index++) { if (array[index] > array[index + 1]) { temp = array[index]; array[index] = array[index + 1]; array[index + 1] = temp; } } } } }

/****************************** 3. Example of code Selectionsort ******************************/ public class ObjectSelectionSort { public static void selectionSort(Comparable[] array) { int startScan; // Starting position of the scan int index; // To hold a subscript value int minIndex; // Element with smallest value in the scan Comparable minValue; // The smallest value found in the scan

for (startScan = 0; startScan < (array.length-1); startScan++) { minIndex = startScan; minValue = array[startScan]; for(index = startScan + 1; index < array.length; index++) { if (array[index].compareTo(minValue) < 0) { minValue = array[index]; minIndex = index; } } array[minIndex] = array[startScan]; array[startScan] = minValue; } } }

/****************************** Example: RecoursiveFibonacciTimer ******************************/ import java.util.Scanner; public class RecursiveFibonacciTimer { public static void main(String[] args) { System.out.println("Enter a positive integer:"); Scanner sc = new Scanner(System.in); int number = sc.nextInt();

long currentTime = System.currentTimeMillis(); long previousTime; long elapsedTime = 0;

for (int k = 0; k <= 5; k++) { previousTime = currentTime; System.out.print("The Fibonacci term at position "); System.out.print((number + k) + " is " ); System.out.println(fib(number + k)); currentTime = System.currentTimeMillis(); elapsedTime = (currentTime - previousTime)/1000; System.out.println("Computed in " + elapsedTime + " seconds."); } } public static long fib(long n) { if (n <=1) return 1; else return fib(n-2) + fib(n-1); } } /******************************