For the Binary Search Algorithm to be effective the data must be ordered. Although we capitalized on the static java.util.Arrays class to do the sorting for us last week, it is necessary to investigate the various algorithms in more depth.

The search for a fast, efficient sorting utility has led to the development of numerous algorithms over the last half-century. Some strategies are easy to understand and code, but can execute relatively slowly. Others are extremely fast, but challenging to understand and maintain. In these exercises, we will explore the details of four important algorithms (Selection, Insertion, Merge and Quicksort).

Once you have a feel for the mechanics of the Selection Sort, complete the following tasks,

1. Create a project called SortingAlgorithms and drop in this driver.
2. Implement the statements required by the comments within the code. Start with an array size of 100. Think: What would be the simplest strategy for obtaining an array of random integers?
3. Implement the display and selectionSort methods. Think: What could be done to limit the bofy of the diaply method to a single statement? Confirm by observation that the elements are being ordered by your selectionSort method.
4. Increase the size of the array by factor of 10, a number of times.

We can get an idea of the amount of time the algorithm takes by invoking the System.currentTimeMillis() method.

5. Modify your selectionSort method to return the number of milliseconds taken to perform the task.
6. Have your driver display the time taken in seconds, to three decimal places, to complete the Selection sort.

7. Modify your driver to produce timing results for array sizes from 0 to 100 000, increasing by 20 000 each time. Format your output as follows,

   

8. Copy the console data to the clipboard and paste it in a blank Excel worksheet
9. Develop an appropriately-annotated line chart to confirm the Big O of this algorithm. Save your workbook as Sorts.xlsx. What do your efforts suggest as a possible Big O for the Selection sort? Explain why this could have been expected.

Insertion Sort

10. Add the method private static void insertionSort(int [] data) to your SortingAlgorithms class that implements the Insertion Sort.
11. Add a call to the method from your driver and records the times for the similar array sizes to yor Excel Worksheet. Add the new data series to theChart and compare. Conclusion?

Merge Sort and Quicksort

12. Add the method private static void mergeSort(int [] data) to your SortingAlgorithms class that implements the Merge Sort.
13. Add a call to the method from your driver and records the times for the similar array sizes to yor Excel Worksheet. Add the new data series to the Line Chart and compare. Conclusion?
14. Add the method private static void quickSort(int [] data) to your SortingAlgorithms class that implements the QuickSort.
15. Add a call to the method from your driver and records the times for the similar array sizes to yor Excel Worksheet. Add the new data series to the Line Chart and compare. Conclusion?