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

Use theSystem.currentTimeMillis()function to measure the speed of your programs. Use the program below as a guide.

import java.io.*; import java.text.*;

//Lets test how fast your computer can process your code! public class speedTest {

//main method public static void main(String[] args) throws IOException { //Some variables to help us out! long time, time2, finalTime; int i;

//Get the current time in milliseconds time = System.currentTimeMillis();

//Output time to the screen System.out.println("The Current Time is: " + time);

//Here is some code for the computer to run. //You may have to change 500 to a higher number //if your computer is really really fast for(i = 0; i < 500; i++) { System.out.print("."); }

//Get the time at the end of the program time2 = System.currentTimeMillis();

//Output the end time and the difference in times! System.out.println(""); System.out.println("The End Time is: "+time2);

finalTime = time2 - time; System.out.println("It took " +finalTime+ " Milliseconds"); }

}

I need the following tasks:

1. need to Compare sorting algorithms: bubble sort and insertion sort.
   1. need to 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.
   2. need to Write the bubble sort method. This method must produce output that states the total run-time of the algorithm, as in the speedTest.java example.
   3. need to Write the insertion sort method. This method must produce output that states the total run-time of the algorithm, as in the speedTest.java example.
   4. 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.
   5. In Big-O notation, compare the worst-case complexities of the two algorithms.
   6. Which is more efficient? Which criteria must be taken into account when choosing a sort algorithm to use the most efficient?
2. need to Compare search algorithms: sequential search and binary search.
   1. Declare and initialize two arrays: one sorted and the other unsorted.
   2. Write the sequential search method. This method must produce output that states the total run-time, as in the speedTest.java example.
   3. Write the binary search method. This method must produce output that states the total run-time, as in the speedTest.java example.
   4. Run the sequential search method and the binary search method on the sorted array. Compare the run times of the two.
   5. Run the sequential search method on the unsorted array. Then call a sort method from (1) to sort the array. Next, call binary search on the sorted array. Compare the run times of the sequential search vs sorting + binary search.
   6. In Big-O notation, compare the worst-case complexities of the two algorithms.
   7. Which search method is more efficient? Is this true for all cases?