In this project you will be implementing several sorting algorithms.

insertion sort

selection sort

shell sort

quick sort

bubble sort

merge sort

heap sort (extra credit)

In addition, each time you run a sorting algorithm, you will be collecting statistics about the sort. The statistics for each sort will include the number of comparisons, the number of data moves, and the time required by the sort. By generating these statistics, we can compare the performance of the different sorting algorithms in practice and see how our results match up with the complexities we derived for each algorithm.

Objectives

Implement basic and faster sorting algorithms

Gain experience writing and using static methods

Gain experience measuring compares, data moves and elapsed time in Java

Analyze the results of your program to better understand how your program behaves

Specifications

The SortObject Class is a class which implements the Comparable interface and is designed to help you count the number of comparisons your code does. It has a class data member that keeps track of the number of comparisons done. Each time the compareTo method is called, the class data member is incremented. The resetCompares method resets the class data member, compares, to 0 and the getCompares method returns the number of comparisons done on SortObjects since the last reset. It also has a class data member that keeps track of the number of assignments done. Each time the assignTo method is called, the class data member is incremented. The resetAssignment method resets the class data member, assignments, to 0 and the getAssignments method returns the number of assignments done on SortObjects since the last reset.

The SortingComparisons Class You will be implementing seven sorting algorithms (insertion, selection, shell, bubble, merge, quick and heap which is optional) and one method that, given an input array, runs each of the algorithms, generates statistics, and prints out the results. All of these methods will be static methods in the SortingComparisons class. Each sort takes a Comparable array as a parameter. Note that nothing is returned. The array that is passed in is modified by the sort so that after the sort is finished the array is in ascending order. The runAllSorts method is passed an array, runs each of the sort algorithms, and displays the following statistics for each sort:

number of comparisons

number of data moves

time (in milliseconds)

All output will go to the console. Note that each sort method will modify the array passed as a parameter. However, in order to compare the behavior of the different sorting algorithms we want to use the same input for each algorithm. Thus, it is important that the runAllSorts method pass identical information to each sort method. Note also that the runAllSorts method should not modify the original array it is passed

The TestSort Class provides a menu for running the program. You need provide two input arguments: the size of array and a random seed (e.g., 500, 12345) each time you running the program. Users are able to choose either running each individual sorting algorithm separately or running them together. It contains the following options:

H: show the help menu

Q: quit the program

D: display the original input data

O: display the output (sorted data) after running a sorting algorithm

R: run all 7 sorting algorithms and print out the statistics

0: run insertion sort

1: run selection sort

2: run shell sort

3: run quick sort

4: run heap sort (extra credit)

5: run bubble sort

6: run merge sort

Summary of provided materials

SortObject.java - do not modify this class

SortingComparisons.java - need to modify this class

TestSort.java - do not modify this class

An Sample output

TestSort [Java Application] C:AProgram FilesJava re1.8.0_144 bin javaw.exe (Oct 29, 2017, 4:09:03 PM Testing program for sorting methods for a contiguous list. User options are: [H]elp [QJuit write [D]ata write sorted [oJutput [R]un all sorting algorithms and get comparison results. [0] insertion sort [1] selection sort [2] shell sort [3] quick sort [4] heap sort [5] bubble sort [6] merge sort Parameters used: # items in input array : 10000 random # seed: 12345 Enter a command of H, Q, o, DJ 0, 1, 2, 3, 4, 5, 6: algorithm data compares data moves milliseconds insertion sort selection sort shell sort quick sort heap sort bubble sort merge sort 24969206 49995000 249014 164833 235302 49995000 120446 24979211 29997 374097 286778 372531 74877639 267232 65 65 212 Enter a command of H, Q, o, DJ 0, 1, 2, 3, 4, 5, 6: TestSort [Java Application] C:AProgram FilesJava re1.8.0_144 bin javaw.exe (Oct 29, 2017, 4:09:03 PM Testing program for sorting methods for a contiguous list. User options are: [H]elp [QJuit write [D]ata write sorted [oJutput [R]un all sorting algorithms and get comparison results. [0] insertion sort [1] selection sort [2] shell sort [3] quick sort [4] heap sort [5] bubble sort [6] merge sort Parameters used: # items in input array : 10000 random # seed: 12345 Enter a command of H, Q, o, DJ 0, 1, 2, 3, 4, 5, 6: algorithm data compares data moves milliseconds insertion sort selection sort shell sort quick sort heap sort bubble sort merge sort 24969206 49995000 249014 164833 235302 49995000 120446 24979211 29997 374097 286778 372531 74877639 267232 65 65 212 Enter a command of H, Q, o, DJ 0, 1, 2, 3, 4, 5, 6