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):
- Line 5: int value = data[i];
- Line 12: data[j+1] = data[j];
- Line 16: data[j+1] = value;
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:
- 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.
- 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.