SEARCHING AND SORTING - Java Programming: From Problem Analysis to Program Design - page 915

sorted list unsorted list

[0] [1] [2] [3] [4] [5] [6] [7]

list 10 18 25 25 30 17 45 35

temp 23

FIGURE 14-10 List after copying list[3] into list[4] , and then list[2] into list[3]

We now copy temp into list[2] . Figure 14-11 shows the resulting list.

u nsorted
list

sorted list

[0] [1] [2] [3] [4] [5] [6] [7]

list 10 18 23 25 30 17 45 35

copy

temp 23

FIGURE 14-11 List after copying temp into list[2]

Now list[0]...list[4] is sorted and list[5]...list[7] is unsorted. We repeat
this process on the resulting list by moving the first element of the unsorted list into the
sorted list in the proper place.
From this discussion, it is clear that during the sorting phase the array containing the
list is divided into two sublists: sorted and unsorted. Elements in the sorted sublist
are sorted; elements in the unsorted sublist are to be moved to the sorted sublist in
their proper places one at a time. We use an index—say, firstOutOfOrder —to
point to the first element in the unsorted sublist. Initially, firstOutOfOrder is
initialized to 1 .
This discussion translates into the following pseudoalgorithm:

for (firstOutOfOrder = 1; firstOutOfOrder < listLength;
firstOutOfOrder++)
if (list[firstOutOfOrder] is less than list[firstOutOfOrder - 1])
{

1
4

copy list[firstOutOfOrder] into temp

initialize location to firstOutOfOrder