Reference no: EM133381301

Programming- Run Time Observation 

Overview
This project is to implement two sorting algorithms. The first sorting algorithm is an ??(??2) algorithm: either Selection Sort or Insertion Sort or Bubble Sort. The second algorithm is Quicksort. Your Quicksort algorithm must use the median-of-three method to determine the pivot, and must use the Hoare Partition algorithm (both described in the book and slides). With all of this done, you will be asked to gather some data about the running time and plot it.

Requirements
You must implement the two sorting algorithms above. They should sort the numbers in ascending order (smallest to largest). When you submit your project, you must have functioning code for both sorting algorithms, but you can comment out the lines in your main method which actually do the sorting (so I can uncomment a single line to switch the sorting algorithm). If you'd like, you can ask the user which sorting algorithm and do it that way.

You must also have a method/function confirmSorted(). This function should take your array of numbers, verify that it is sorted in ascending order, and return a Boolean. If the numbers are
confirmed to be sorted, print out "Confirmed sorted" and if they aren't sorted, print out "Confirmed NOT sorted". Do this before and after the sort.

Data analysis
In addition to your code, you'll be asked to try out each sorting algorithm will datasets of different sizes and record the running time (in milliseconds). With this data, you should create a table and
graph like the one below. In a paragraph or two, please write what you've discovered with this data,
explain what is happening with the data and why.

You will be provided with datasets of the following sizes: 10, 100, 1000, 5000, 10000, 25000, 50000,
75000, 100000, 250000, 500000, 750000, 1000000, and 10000000. Please include results for all

these datasets in your analysis. Some combinations of algorithm and dataset size won't be feasible
and may be excluded (the slower algorithm will start to take a VERY long time with large datasets).

Extra credit:
Implement the classic Merge Sort algorithm and compare the usage of the memory between Merge Sort and Quick Sort (or one of the basic sorting algorithms)