An Introduction to Sorting - Data Structures and Abstractions with Java - page 207

// break chain into 2 pieces: sorted and unsorted
Node unsortedPart = firstNode.getNextNode();
assert unsortedPart != null ;
firstNode.setNextNode( null );
while (unsortedPart != null )
{

Node nodeToInsert = unsortedPart;
unsortedPart = unsortedPart.getNextNode();
insertInOrder(nodeToInsert);
} // end while
} // end if
} // end insertionSort

Question 3 In the previous method insertionSort , if you move the line
unsortedPart = unsortedPart.getNextNode();
after the call to insertInOrder , will the method still work? Explain.

Question 4 The previous method insertionSort is not a static method. Why?

8.20

The efficiency of an insertion sort of a chain. For a chain of n nodes, the number of comparisons
that the method insertInOrder makes is at most the number of nodes in the sorted portion of the
chain. The method insertionSort calls insertInOrder n - 1 times. The first time it does so, the
sorted portion contains one item, so one comparison is made. The second time, the sorted portion
contains two items, so at most two comparisons are made. Continuing in this fashion, you can see
that the maximum number of comparisons is

1 + 2 + … + ( n - 1)

This sum is n ( n - 1) / 2, so this insertion sort is O( n 2 ).

Note: Sorting a chain of linked nodes can be difficult. The insertion sort, however, pro-
vides a reasonable way to perform this task.

Shell Sort

8.21

The sorting algorithms that we have discussed so far are simple and often useful, but they are too inef-
ficient to use on large arrays. The Shell sort is a variation of the insertion sort that is faster than O( n 2 ).
During an insertion sort, an array entry moves to an adjacent location. When an entry is far from
its correct sorted position, it must make many such moves. So when an array is completely scrambled,
an insertion sort takes a good deal of time. But when an array is almost sorted, an insertion sort is
more efficient. In fact, Segment 8.15 showed that the more sorted an array is, the less work the
method insertInOrder needs to do.
By capitalizing on these observations, Donald Shell devised in 1959 an improved insertion
sort, now called the Shell sort . Shell wanted entries to move beyond their adjacent locations. To do
so, he sorted subarrays of entries at equally spaced indices. Instead of moving to an adjacent loca-
tion, an entry moves several locations away. The result is an array that is almost sorted—one that
can be sorted efficiently by using an ordinary insertion sort.

8.22

For example, Figure 8-12 shows an array and the subarrays obtained by considering every sixth
entry. The first subarray contains the integers 10, 9, and 7; the second subarray contains 16 and 6;
and so on. There happen to be six of these subarrays.