Java Reference
In-Depth Information
Now we sort each of the six subarrays separately by using an insertion sort. Figure 8-13 shows
the sorted subarrays and the state of the original array as a result. Notice that the array is “more
sorted” than it was originally.
FIGURE 8-12
An array and the subarrays formed by grouping entries whose
indices are 6 apart
0
1
2
3
4
5
6
7
8
9
10
11
12
10
16
11
4
15
3
9
6
1
17
8
12
7
10
9
7
16
6
11
1
17
4
15
8
3
12
FIGURE 8-13
The subarrays of Figure 8-12 after each is sorted, and the array
that contains them
7
9
10
6
16
1
11
17
4
8
15
3
12
7
6
1
4
8
3
9
16
11
17
15
12
10
0
1
2
3
4
5
6
7
8
9
10
11
12
8.23
Now we form new subarrays, but this time we reduce the separation between indices. Shell sug-
gested that the initial separation between indices be n / 2 and that you halve this value at each pass
until it is 1. The array in our example has 13 entries, so we began with a separation of 6. We now
reduce the separation to 3. Figure 8-14 shows the resulting subarrays, and Figure 8-15 shows the
subarrays after they are sorted.
FIGURE 8-14
The subarrays of the array in Figure 8-13 formed by grouping
entries whose indices are 3 apart
0
1
2
3
4
5
6
7
8
9
10
11
12
7
6
1
4
8
3
9
16
11
17
15
12
10
10
7
4
9
17
6
8
16
15
11
1
3
12
Search WWH ::




Custom Search