Java 6 Illuminated: An Active Learning Approach, 2nd Edition

516 CHAPTER 8 Single-Dimensional Arrays

Figure 8.23a

The next card to insert

is a 4

Figure 8.23b

9 is shifted to the right

8.6.3 Insertion Sort

Like Selection Sort, Insertion Sort also derives its name from the algorithm

used to sort the array. The basic approach to an Insertion Sort is to sort ele-

ments much like a card player arranges the cards in sorted order in his or

her hand. The player inserts cards one at a time in such a way that the cards

on the left side of his or her hand are sorted at all times; the cards on the

right side of his or her hand have not yet been inserted into the sorted part

of the hand. As Figure 8.23a shows, the three yello ...