Java Reference
In-Depth Information
figure 8.5
Shellsort after each
pass if the increment
sequence is {1, 3, 5}
Original
81
94
11
96
12
35
17
95
28
58
41
75
15
After 5-sort
35
17
11
28
12
41
75
15
96
58
81
94
95
After 3-sort
28
12
11
35
15
41
58
17
94
75
81
96
95
After 1-sort
11
12
15
17
28
35
41
58
75
81
94
95
96
and are sorted relative to each other. Similarly, after a 3-sort, elements spaced
three apart are guaranteed to be in sorted order, relative to each other. An
important property of Shellsort (which we state without proof ) is that an
h
k
-
sorted array that is then
h
k
-1
-sorted remains
h
k
-sorted. If this were not the
case, the algorithm would likely be of little value because work done by early
phases would be undone by later phases.
In general, an
h
k
-sort requires that, for each position
i
in
,
,
, we place the element in the correct spot among
,
and
so on. Although this order does not affect the implementation, careful exami-
nation shows that an
h
k
-sort performs an insertion sort on
h
k
independent sub-
arrays (shown in different shades in Figure 8.5). Therefore, not surprisingly,
in Figure 8.7, which we come to shortly, lines 9 to 17 represent a
gap inser-
tion sort
. In a gap insertion sort, after the loop has been executed, elements
separated by a distance of
gap
in the array are sorted. For instance, when
gap
is
1, the loop is identical, statement by statement, to an insertion sort.Thus
Shellsort is also known as
diminishing gap sort
.
h
k
h
k
A
diminishing gap
sort
is another
name for Shellsort.
+
1
ii h
k
,
-
,
i
-
2
h
k
…
N
1
,
-
As we have shown, when
gap
is 1 the inner loop is guaranteed to sort the
array
a
. If
gap
is never 1, there is always some input for which the array cannot
be sorted. Thus Shellsort sorts so long as
gap
eventually equals 1. The only
issue remaining, then, is to choose the increment sequence.
Shell suggested starting
gap
at and halving it until it reaches 1, after
which the program can terminate. Using these increments, Shellsort repre-
sents a substantial improvement over the insertion sort, despite the fact that it
nests three
for
loops instead of two, which is usually inefficient. By altering
the sequence of gaps, we can further improve the algorithm's performance. A
summary of Shellsort's performance with three different choices of increment
sequences is shown in Figure 8.6.
Shell's increment
sequence is an
improvement over
the insertion sort
(although better
sequences are
known).
N
2
⁄
8.4.1
performance of shellsort
The running time of Shellsort depends heavily on the choice of increment
sequences, and in general the proofs can be rather involved. The average-case
Search WWH ::
Custom Search