Java Reference
In-Depth Information
Shellsort
N
Insertion Sort
Shell's Increments
Odd Gaps Only
Dividing by 2.2
10,000
575
10
11
9
20,000
2,489
23
23
20
40,000
10,635
51
49
41
80,000
42,818
114
105
86
160,000
174,333
270
233
194
320,000
NA
665
530
451
640,000
NA
1,593
1,161
939
figure 8.6
Running time of the insertion sort and Shellsort for various increment sequences
analysis of Shellsort is a long-standing open problem except for the most triv-
ial increment sequences.
When Shell's increments are used, the worst case is O ( N 2 ) . This bound is
achievable if N is an exact power of 2, all the large elements are in even-
indexed array positions, and all the small elements are in odd-indexed array
positions. When the final pass is reached, all the large elements will still be in
the even-indexed array positions, and all the small elements will still be in the
odd-indexed array positions. A calculation of the number of remaining inver-
sions shows that the final pass will require quadratic time. The fact that this is
the worst that can happen follows from the fact that an h k -sort consists of h k
insertion sorts of roughly N / h k elements. Thus the cost of each pass is
O ( h k ( N / h k ) 2 ), or O ( N 2 / h k ). When we sum this cost over all the passes, we
obtain O ( N 2
In the worst case,
Shell's increments
give quadratic
behavior.
Σ1 / h k ). The increments are roughly a geometric series, so the sum
is bounded by a constant. The result is a quadratic worst-case running time.
We can also prove via a complex argument that when N is an exact power of 2
the average running time is O ( N 3/2 ) . Thus, on average, Shell's increments
give a significant improvement over insertion sort.
A minor change to the increment sequence can prevent the quadratic
worst case from occurring. If we divide gap by 2 and it becomes even, we
can add 1 to make it odd. We can then prove that the worst case is not qua-
dratic but only O ( N 3/2 ). Although the proof is complicated, the basis for it
is that in this new increment sequence, consecutive increments share no
common factors (whereas in Shell's increment sequence they do). Any
sequence that satisfies this property (and whose increments decrease
If consecutive
increments are rel-
atively prime, the
performance of
Shellsort is
improved.
 
Search WWH ::




Custom Search