Computational Complexity
The following property holds: after h2-sorting of any h1-sorted array, the array remains h1-sorted. Every h1-sorted and h2-sorted array is also (a1h1+a2h2)-sorted, for any nonnegative integers a1 and a2. The worst-case complexity of Shellsort is therefore connected with the Frobenius problem: for given integers h1,..., hn with gcd = 1, the Frobenius number g(h1,..., hn) is the greatest integer that cannot be represented as a1h1+ ... +anhn with nonnegative integer a1,..., an. 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 proven results concerns a practical gap sequence. For gaps that are powers of two, Espelid computed this average as . Knuth determined the average complexity of sorting an N-element array with two gaps (h, 1) to be . It follows that a two-pass Shellsort with h = Θ(N1/3) makes on average O(N5/3) comparisons. Yao found the average complexity of a three-pass Shellsort. His result was refined by Janson and Knuth: the average number of comparisons made during a Shellsort with three gaps (ch, cg, 1), where h and g are coprime, is in the first pass, in the second pass and in the third pass. ψ(h, g) in the last formula is a complicated function asymptotically equal to . In particular, when h = Θ(N7/15) and g = Θ(h1/5), the average time of sorting is O(N23/15).
Based on experiments, it is conjectured that Shellsort with Hibbard's and Knuth's gap sequences runs in O(N5/4) average time, and that Gonnet and Baeza-Yates's sequence requires on average 0.41NlnN(ln lnN+1/6) element moves. 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.e. log2N!, where the sequence 1, 4, 10, 23, 57, 132, 301, 701 has been extended according to the formula .
Applying the theory of Kolmogorov complexity, Jiang, Li, and Vitányi proved the following lower bounds for the order of the average number of operations in an m-pass Shellsort: Ω(mN1+1/m) when m≤log2N and Ω(mN) when m>log2N. Therefore Shellsort has prospects of running in an average time that asymptotically grows like NlogN only when using gap sequences whose number of gaps grows in proportion to the logarithm of the array size. It is, however, unknown whether Shellsort can reach this asymptotic order of average-case complexity, which is optimal for comparison sorts.
The worst-case complexity of any version of Shellsort is of higher order: Plaxton, Poonen, and Suel showed that it grows at least as rapidly as Ω(N(logN/log logN)2).
Read more about this topic: Shellsort
Famous quotes containing the word complexity:
“It is not only their own need to mother that takes some women by surprise; there is also the shock of discovering the complexity of alternative child-care arrangements that have been made to sound so simple. Those for whom the intended solution is equal parenting have found that some parents are more equal than others.”
—Elaine Heffner (20th century)