Arrays - Multimedia Introduction to Programming Using Java - page 272

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