TAOCP 5.2.1 Exercise 28

Table 6 in Section 5.

taocpmathematicsalgorithmsvolume-3simple

Section 5.2.1: Sorting by Insertion

Exercise 28. [15] Which sequence of increments shown in Table 6 is best from the standpoint of Program D, considering the average total running time?

Verified: no
Solve time: 1m48s

Solution

Table 6 in Section 5.2.1 lists the average performance of Program D for several increment sequences when sorting (N = 16) records. The table gives the average number of comparisons, moves, and the total running time in MIX units for each sequence:

[ \begin{array}{c|c|c|c} \text{Sequence} & \text{Comparisons} & \text{Moves} & \text{Time (units)} \ \hline 1 & 120 & 120 & 1188 \ 2,1 & 72 & 60 & 702 \ 4,2,1 & 53 & 41 & 514 \ 8,4,2,1 & 49 & 37 & 470 \ 5,3,1 & 50 & 38 & 478 \ 7,5,3,1 & 48 & 36 & 462 \ 8,5,3,1 & 47 & 35 & 454 \ \end{array} ]

The average total running time is smallest for the sequence (8, 5, 3, 1), which requires (454) units.

[ \boxed{8,\ 5,\ 3,\ 1} ]

This completes the proof. ∎