Due Date: Monday, March 21 or Tuesday, March 22, depending on the day of your lab.
Objective: The goal of this assignment is to practice sorting.
Assignment: Implement all four sorting methods described
in the book: insertion sort, shell sort, merge sort, and quick sort.
For each of these methods,
A reasonable way to write a pedagogical implementation is to
write an auxiliary method that displays all the elements of
the array and waits for the user's reaction; then, every time
you change an element of the array while sorting it, you call
this auxiliary method.
- write a regular implementation in which the method simply
returns the sorted array, and
- write a pedagogical implementation in
which, every time we change an element of an array, the method shows
the new state of the array and waits for the user to hit Return
For extra credit: Use techniques described in Assignment 3 to
record the computation time needed for
each sorting method; for sizes n = 10, 20, 30, and 40
run each several times (e.g., 100) with a randomly generated array and
record, for each of the four methods,
how the average running time grows as a function of n.