Arrays - Multimedia Introduction to Programming Using Java - page 287

Further, mathematical analysis has shown that stopping when v is found saves,
on the average, only one iteration. Thus, it is not worth it. Further, this binary
search has three other advantages over most of the other binary searches that you
will see in the literature:

1. It works when the array is empty (when h=k+1 ).
2. Binary searches that stop when v is found find only a random v , and not
the rightmost one.
3. Binary searches that stop when v is found do not produce any indication
of where v should go if v is not in the array.
Moreover, this binary search algorithm is memorable ; just remember the post-
condition and how you get the invariant from the postcondition, and you can eas-
ily develop the algorithm whenever necessary.

8.5.4 Selection sort

By an array b being “sorted” we mean that its values are in ascending order: i<
j implies that b[i] ≤ b[j] . To sort an array means to place its values in ascend-
ing order. We also say that an array is sorted in descending order if i<j implies
that b[i] ≥ b[j] .
Sorting is a fundamental process in computing. Here, we look at one sort-
ing algorithm, selectionSort . Another one, insertionSort , is described in
ProgramLive activity 8-6.3. Both of these sort algorithms are “quadratic” algo-
rithms, in both the average case and worst case. This means that for an array of
size n (say), their execution times are proportional to n 2 . For example, it will
take 10,000 units of time to sort an array of 100 elements. Faster sorting algo-
rithms exist. Two of them, quickSort and mergeSort , are developed in Chap.
15.

Activity
8-6.1

We want a procedure that satisfies this specification:

/** Sort b: put its elements in non-descending order */
public static void selectionSort( int [] b)
The body of the procedure is a loop. For its loop invariant we choose:

/** Sort b —put its elements in ascending order */
public static void selectionSort( int [] b) {
// inv P: 0 ≤ i < b.length and b[0..j-1] is sorted and b[0..j-1] ≤ b[j..]
for ( int j= 0; j != b.length; j= j + 1) {
int p= the index of the minimum value of b[j..];
// {b[p] is min of b[j..]}
Swap b[j] and b[p]

}

}
Figure 8.8: Abstract view of SelectionSort