Java Reference

In-Depth Information

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

Search WWH ::

Custom Search