Question

Problem 4 . Hibbard’s gap sequence for Shellsort is defined as follows.

2 k − 1, 2 k−1 − 1, 2 k−2 − 1, . . . , 7, 3, 1

where k is the largest number satisfying 2k − 1 < N.

(b) Implement Shellsort with Hibbard’s gap sequence, with Shell’s gap sequence, and with a gap sequence of your own invention, and compare them on three input/output examples for duplicate-free arrays of size 10, 100, and 1000 (one of each size). Report the number of comparisons made in each case.

Answer 1