Quiz 6, 10/4

The program TimingSimpleSort.java times the three sorting algorithms, insertion sort, bubble sort, and selection sort. It uses the Java timer to do so. Another way to "time" these sorting algorithms is by counting the number of comparisons and the number of data items moved.

To be precise, let us define a data item move as an assignment that involves a slot of the array being sorted. For example, in the implementation of insertionSort in TimingSimpleSort.java, there are three lines that perform a data move (according to this definition):

Also note that bubbleSort and selectionSort make calls to swap to move data around; each call to swap makes 3 data moves.

This quiz requires you to do two things:

  1. Modify all 3 sorting methods in TimingSimpleSort.java so that they return the total number of comparisons plus the number of data item moves. Thus the return type of these functions will no longer be void; it needs to be changed to int.
  2. Then modify the main method so that it prints out, in addition to the average running times, also the average number of comparisons plus data moves, for each value of n.