Data Structures, Algorithms, & Applications in Java
Chapter 4, Exercise 5

This exercise has been substantially done in Exercises 2, 3, and 4.

(a)

The worst-case data for bubble sort is a descending sequence (see solution to Exercise 3) and for selection sort is an ascending sequence terminated by a small value (see Exercise 4).

(c)

The table can be derived from the data given in the solutions to Exercises 2, 3, and 4.

(d)

Insertion sort has the best worst-case performance followed by selection sort. Bubble sort has the poorest worst-case performance.

(e)

The overhead time included in the insertion sort and bubble sort measurements is the same. This is given in Figure 4.4 of the text. The selection sort overhead time is slightly larger.

(f)

The conclusions remain the same.

(g)

Since the worst case complexity of each of the sort methods is Theta(n2) we can estimate the worst case time needed to sort n numbers using that to sort 1000 numbers. t(n) / t(1000) approxmately equals n2 / (1000)2. So, t(n) approximately equals n2t(1000) / 106. In particular, t(2000) approximately equals 4t(1000), t(4000) approximately equals 16t(1000), and t(10000) approximately equals 100t(1000). Using these formulas and the measured values of t(1000), we can estimate the required times.