Shellsort - Gap Sequences

Gap Sequences

Every gap sequence that contains 1 yields a correct sort; however, the properties of thus obtained versions of Shellsort may be very different.

The table below compares most proposed gap sequences published so far. Some of them have decreasing elements that depend on the size of the sorted array (N). Others are increasing infinite sequences, whose elements less than N should be used in reverse order.

General term (k ≥ 1) Concrete gaps Worst-case
time complexity
Author and year of publication
leftlfloorfrac{N}{2}rightrfloor, leftlfloorfrac{N}{4}rightrfloor, ldots, 1 Shell, 1959
Frank & Lazarus, 1960
Hibbard, 1963
, with 1 prepended Papernov & Stasevich, 1965
successive numbers of the form Pratt, 1971
, not greater than Knuth, 1973
prod limits_{scriptscriptstyle 0le q<ratop scriptscriptstyle qneq(r^2+r)/2-k}a_q, hbox{where}
Incerpi & Sedgewick, 1985
, with 1 prepended Sedgewick, 1986
Sedgewick, 1986
? Gonnet & Baeza-Yates, 1991
? Tokuda, 1992
unknown ? Ciura, 2001

When the binary representation of N contains many consecutive zeroes, Shellsort using Shell's original gap sequence makes Θ(N2) comparisons in the worst case. For instance, this case occurs for N equal to a power of two when elements greater and smaller than the median occupy odd and even positions respectively, since they are compared only in the last pass.

Although it has higher complexity than the O(NlogN) that is optimal for comparison sorts, Pratt's version lends itself to sorting networks and has the same asymptotic gate complexity as Batcher's bitonic sorter.

Gonnet and Baeza-Yates observed that Shellsort makes the fewest comparisons on average when the ratios of successive gaps are roughly equal to 2.2. This is why their sequence with ratio 2.2 and Tokuda's sequence with ratio 2.25 prove efficient. However, it is not known why this is so. Sedgewick recommends to use gaps that have low greatest common divisors or are pairwise coprime.

With respect to the average number of comparisons, the best known gap sequences are 1, 4, 10, 23, 57, 132, 301, 701 and similar, with gaps found experimentally. Optimal gaps beyond 701 remain unknown, but good results can be obtained by extending the above sequence according to the recursive formula .

Tokuda's sequence, defined by the simple formula, where, can be recommended for practical applications.

Read more about this topic:  Shellsort

Other articles related to "gap sequences, gap sequence, gaps":

Shellsort - Computational Complexity
... numbers, we can determine the worst-case complexity of Shellsort for several classes of gap sequences ... of proven results concerns a practical gap sequence ... For gaps that are powers of two, Espelid computed this average as ...

Famous quotes containing the word gap:

    Great talkers are trying to fill the gap between themselves and others, but only widen it.
    Mason Cooley (b. 1927)