Java Reference
In-Depth Information
59
20
17
13
28
14
23
83
36
98
11
70
65
41
42
15
36
20
11
13
28
14
23
15
59
98
17
70
65
41
42
83
28
14
11
13
36
20
17
15
59
41
23
70
65
98
42
83
11
13
17
14
23
15
28
20
36
41
42
70
59
83
65
98
11
13
14
15
17
20
23
28
36
41
42
59
65
70
83
98
Figure7.6
An example of Shellsort. Sixteen items are sorted in four passes.
The first pass sorts 8 sublists of size 2 and increment 8. The second pass sorts
4 sublists of size 4 and increment 4. The third pass sorts 2 sublists of size 8 and
increment 2. The fourth pass sorts 1 list of size 16 and increment 1 (a regular
Insertion Sort).
sublists of 2 elements each, where the array index of the 2 elements in each sublist
differs by n=2. If there are 16 elements in the array indexed from 0 to 15, there
would initially be 8 sublists of 2 elements each. The first sublist would be the ele-
ments in positions 0 and 8, the second in positions 1 and 9, and so on. Each list of
two elements is sorted using Insertion Sort.
The second pass of Shellsort looks at fewer, bigger lists. For our example the
second pass would have n=4 lists of size 4, with the elements in the list being n=4
positions apart. Thus, the second pass would have as its first sublist the 4 elements
in positions 0, 4, 8, and 12; the second sublist would have elements in positions 1,
5, 9, and 13; and so on. Each sublist of four elements would also be sorted using
an Insertion Sort.
The third pass would be made on two lists, one consisting of the odd positions
and the other consisting of the even positions.
The culminating pass in this example would be a “normal” Insertion Sort of all
elements. Figure 7.6 illustrates the process for an array of 16 values where the sizes
of the increments (the distances between elements on the successive passes) are 8,
4, 2, and 1. Figure 7.7 presents a Java implementation for Shellsort.
Shellsort will work correctly regardless of the size of the increments, provided
that the final pass has increment 1 (i.e., provided the final pass is a regular Insertion
Sort). If Shellsort will always conclude with a regular Insertion Sort, then how
can it be any improvement on Insertion Sort? The expectation is that each of the
(relatively cheap) sublist sorts will make the list “more sorted” than it was before.
