Programming and Problem Solving with Java

(^540) | Array-Based Lists
Going back to our by-hand algorithm, we can search listItemsfor the smallest value, but
how do we “cross off” a list component? We could simulate crossing off a value by replacing
it with null. In this way, we set the value of the crossed-off item to something that doesn’t
interfere with the processing of the rest of the components. However, a slight variation of our
hand-done algorithm allows us to sort the components in place. We do not have to use a sec-
ond list; we can, instead, put a value into its proper place in the list by having it swap places
with the component currently in that list position.
We can state the algorithm as follows: We search for the smallest value in the array
holding the items and exchange it with the component in the first position in the array.
We search for the next-smallest value in the array and exchange it with the component in
the second position in the array. This process continues until all components are in their
proper places.
Figure 11.4 illustrates how this algorithm works.
Observe that we perform numItems – 1 passes through the list because countruns from
0 through numItems – 2. The loop does not need to be executed when countequals numItems –
1 because the last value,listItems[numItems – 1], is in its proper place after the preceding com-
ponents have been sorted.
This algorithm, known as the straight selection sort,belongs to a class of sorts called se-
lection sorts. Many types of sorting algorithms exist. Selection sorts are characterized by
finding the smallest (or largest) value left in the unsorted portion at each iteration and swap-
ping it with the value indexed by the iteration counter. Swapping the contents of two vari-
ables requires a temporary variable so that no values are lost (see Figure 11.5).
selectSort
forcount going from 0 through numItems – 2
Find the minimum value in listItems[count]..listItems[numItems – 1]
Swap minimum value with listItems[count]
[0] judy
[1] susy
[2] betty
[3] sarah
[4] ann
june
ann
susy
betty
sarah
judy
june
ann
betty
susy
sarah
judy
june
ann
betty
judy
sarah
susy
june
ann
betty
judy
june
susy
sarah
ann
betty
judy
june
sarah
[5] susy
Figure 11.4 Straight Selection Sort
T
E
A
M
F
L
Y
Team-Fly®