Shellsort with gaps 23, 10, 4, the art of computer programming sorting and searching pdf in action. Vectorgraphic diagram depicting the step-by-step process. The step-by-step process of replacing pairs of items during the shell sorting algorithm. The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared.
Starting with far apart elements, it can move some out-of-place elements into position faster than a simple nearest neighbor exchange. The running time of Shellsort is heavily dependent on the gap sequence it uses. 1 is guaranteed to leave a sorted list in the end. An example run of Shellsort with gaps 5, 3 and 1 is shown below. In both cases insertion sort works efficiently. Using Marcin Ciura’s gap sequence, with an inner insertion sort. Do a gapped insertion sort for this gap size.
The question of deciding which gap sequence to use is difficult. Shellsort may be very different. Too few gaps slows down the passes, and too many gaps produces an overhead. The table below compares most proposed gap sequences published so far. Gonnet and Baeza-Yates observed that Shellsort makes the fewest comparisons on average when the ratios of successive gaps are roughly equal to 2. This is why their sequence with ratio 2.
2 and Tokuda’s sequence with ratio 2. However, it is not known why this is so. Using known formulae for Frobenius numbers, we can determine the worst-case complexity of Shellsort for several classes of gap sequences. Proven results are shown in the above table. With respect to the average number of operations, none of the proven results concerns a practical gap sequence. Gonnet and Baeza-Yates’s sequence requires on average 0.
Approximations of the average number of operations formerly put forward for other sequences fail when sorted arrays contain millions of elements. The graph below shows the average number of element comparisons in various variants of Shellsort, divided by the theoretical lower bound, i. It is, however, unknown whether Shellsort can reach this asymptotic order of average-case complexity, which is optimal for comparison sorts. The Art of Computer Programming.