Analysis of Algorithms : An Active Learning Approach

72 SORTING ALGORITHMS

If there are just two passes, it has been shown that using an increment of

about for the first pass and 1 for the second pass produces a sort of

O(N5/3).

Another set of increments would be hj = (3j
 1) / 2 for all h values less

thanN. These values also satisfy the relationship hj+1 = 3hj + 1 and h 1 = 1, so

once the largest value of h is identified, succeeding increments can be calcu-

lated by hj = (hj+1 – 1) / 3. Using this sequence of increments results in a sort of

O(N3/2).

Another version will calculate all of the possible values of 2i 3 j (for any inte-

gers i≥ 0 and j≥ 0) that are less than the size of the list and use those values in

decreasing order. For example, if N is 40, we would have the following

sequence of increments: 36 (2^232 ), 32 (2^530 ), 27 (2^033 ), 24 (2^331 ), 18 (2^132 ), 16

(2^430 ), 12 (2^231 ), 9 (2^032 ), 8 (2^330 ), 6 (2^131 ), 4 (2^230 ), 3 (2^031 ), 2 (2^130 ), and 1

(2^030 ). By using a sequence of values that follows this pattern, shellsort’s order

can be reduced to O(N(lgN)^2 ). It should be noted that the large number of

passes introduces significant overhead, so this doesn’t become a practical

sequence unless the size of the list is very large.

Shellsort is unique in that its general algorithm stays the same, but the

choices of its parameters can have a dramatic effect on its order.

3.3.3

1. Show the results of each of the passes of Shellsort using the increments
   of 7, 5, 3, and 1 with the initial list of values [16, 15, 14, 13, 12, 11, 10, 9,
   8, 7, 6, 5, 4, 3, 2, 1]. How many comparisons are done?


2. Show the results of each of the passes of Shellsort using the increments
   of 8, 4, 2, and 1 with the initial list of values [16, 15, 14, 13, 12, 11, 10, 9,
   8, 7, 6, 5, 4, 3, 2, 1]. How many comparisons are done?


3. Show the results of each pass of Shellsort using increments of 5, 2, and 1
   applied to the list [7, 3, 9, 4, 2, 5, 6, 1, 8]. How many comparisons are
   done?


4. Show the results of each pass of Shellsort using increments of 5, 2, and 1
   applied to the list [3, 5, 2, 9, 8, 1, 6, 4, 7]. How many comparisons are
   done?


5. Write the new version of InsertionSort used in this section.


6. This section looked at sorting as the removal of inversions in a list. For a list
   ofN elements, what is the formula for the largest number of inversions that

1.72 *^3 N

■3.3.3 EXERCISES