Java Reference

In-Depth Information

Programming tip:
When you draw horizontal arrays, do not place a variable (e.g.
m
) directly

over a boundary, as shown below, because you cannot tell whether it marks the

end of the preceding segment or the beginning of the following segment. This

ambiguity leads to confusion. It will not make your instructor chuckle.

0 m

b

and the third segment contains all but the first array element. To picture this men-

tally, think of dragging
i
all the way to
0
. That squishes the first segment and

stretches the right segment to take up most of the array.

8.2.3

Placing information in a segment

We can place information within a segment to describe its properties. In the

example below, we place “
< 3
” in segment
c[0..i-1]
to assert that all its ele-

ments are less than
3
. Similarly, we place “
= 2
” in the right segment to indicate

that all its elements equal
2
.

This picture describes a relationship between the contents of array
c
and

Activity

8-2.3

0

i

c.length

< 3

5

= 2

c

integer variable
i
. We call this relation
P
. We can write
P
without using a picture:

P: c[0..i-1] < 3
and
c[i] = 5
and
c[i+1..] = 2

Whether you prefer the picture or the formula is a matter of taste. The pic-

ture is easier to understand for most people, while the second version is usually

easier to work with when developing an algorithm.

Relations may be true or false, depending on the values of the variables they

reference. For example,
P
is a false statement if the first element of
c
is
4
, no mat-

ter what the value of
i
. And
P
is true if
i=0
and
c
contains
{5
,
2
,
2
,
2}
—the

first segment is empty, so every element in that segment is indeed less than
3
; the

second segment contains a
5
; and the third segment is all
2
's.

Below are two more examples of relations. Relation
Q1
says that the first

segment
b[0..i-1]
is sorted, which means that its values are in non-descending

order. For example,
Q1
is true if
i=4
and
b={1
,
3
,
4
,
4
,
-5
,
2}
but is false if
i

=3
and
b={1
,
4
,
3
,
3
,
6
,
8
,
2}
. Relation
Q1
is used later in algorithm

insertionSort
, which sorts array
b
.

0 i b.length

Q1: b

sorted

Search WWH ::

Custom Search