Assignment: The Great Java Race!

This assignment will explore the difference in run-times and complexities of search algorithms and sorting algorithms.

Use the System.currentTimeMillis() function to measure the speed of your programs. You can use the program below as a guide.

1. Compare sorting algorithms: bubble sort and insertion sort. Write two methods that populate an array- one that populates the array in reverse order, the other that populates the array in a nearly sorted fashion. Write the bubble sort method. This method must produce output that states the total run-time of the algorithm, just like in the speedTest.java example. Write the insertion sort method. This method must produce output that states the total run-time of the algorithm, just like in the speedTest.java example. Initialize an integer array using the methods from (a) and run each sort on the unsorted array. Compare the run times between the two different array arrangements and the two different sorting methods. In Big-O notation, compare the worst-case complexities of the two algorithms. Are either more efficient? What criteria must be taken into account when choosing a sort algorithm to use the most efficient.

2. Compare search algorithms: sequential search and binary search Declare and initialize two arrays: one sorted and the other unsorted. Write the sequential search method. This method must produce output that states the total run-time, just like in the speedTest.java example. Write the binary search method. This method must produce output that states the total run-time, just like in the speedTest.java example. Run the sequential search method and the binary search method on the sorted array. Compare the run times of the two. Run the sequential search method on the unsorted array, then call a sort method from (1) to sort the array then call binary search on the sorted array. Compare the run times of the sequential search vs sorting + binary search. In Big-O notation, compare the worst-case complexities of the two algorithms. Which search method is more efficient? Is this true for all cases? Exceed the Expectations: Use the ArrayList class instead of a 1D array.