Java Reference
In-Depth Information
9.6 Shell (Diminishing Increment) Sort
Shell sort (named after Donald Shell) uses a series of
increments
to govern the sorting process. It makes several
passes over the data, with the last pass being the same as insertion sort. For the other passes, elements that are a fixed
distance apart (for instance, five apart) are sorted using the same technique as insertion sort.
For example, to sort the following array, we use three increments—8, 3, and 1:
num
67
90
28
84
29
58
25
32
16
64
13
71
82
10
51
57
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
The increments decrease in size (hence the term
diminishing increment sort
), with the last one being 1.
Using increment 8, we eight-sort the array. This means we sort the elements that are eight apart. We sort elements
1 and 9, 2 and 10, 3 and 11, 4 and 12, 5 and 13, 6 and 14, 7 and 15, and 8 and 16. This will transform
num
into this:
16
64
13
71
29
10
25
32
67
90
28
84
82
58
51
57
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Next, we three-sort the array; that is, we sort elements that are three apart. We sort elements (1, 4, 7, 10, 13, 16),
(2, 5, 8, 11, 14), and (3, 6, 9, 12, 15). This gives us the following:
16
28
10
25
29
13
57
32
51
71
58
67
82
64
84
90
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Note that, at each step, the array is a little closer to being sorted. Finally, we perform a one-sort, sorting the entire
list, giving the final sorted order:
10
13
16
25
28
29
32
51
57
58
64
67
71
82
84
90
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
You may ask, why didn't we just do a one-sort from the beginning and sort the entire list? The idea here is that
when we reach the stage of doing a one-sort, the array is more or less in order, and if we use a method that works
better with partially ordered data (such as insertion sort), then the sort can proceed quickly. Recall that insertion sort
can take as few as
n
comparisons (if the data is already sorted) or as many as ½
n
2
comparisons (if the data is sorted in
descending order and we want ascending) to sort a list of
n
items.
When the increment is large, the pieces to sort are small. In the example, when the increment is eight, each piece
consists of two elements only. Presumably, we can sort a small list quickly. When the increment is small, the pieces to
sort are bigger. However, by the time we get to the small increments, the data is partially sorted, and we can sort the
pieces quickly if we use a method that takes advantage of order in the data.
We will use a slightly modified version of insertion sort to sort elements that are
h
apart rather than one apart.
In insertion sort, when we come to process
num[k]
, we assume that
num[1..k-1]
are sorted and insert
num[k]
among the previous items so that
num[1..k]
are sorted.
Suppose the increment is
h
, and consider how we might process
num[k]
where
k
is any valid subscript.
Remember, our goal is to sort items that are
h
apart. So, we must sort
num[k]
with respect to
num[k-h]
,
num[k-2h]
,
num[k-3h]
, and so on, provided these elements fall within the array. When we come to process
num[k]
, if the previous
items that are
h
apart are sorted among themselves, we must simply insert
num[k]
among those items so that the
sublist ending at
num[k]
is sorted.
To illustrate, suppose
h
= 3 and
k
= 4. There is only one element before
num[4]
that is three away, that is,
num[1]
.
So, when we come to process
num[4]
, we can assume that
num[1]
, by itself, is sorted. We insert
num[4]
relative to
num[1]
so that
num[1]
and
num[4]
are sorted.
Search WWH ::
Custom Search