Java Reference

In-Depth Information

E10.
Write a procedure that changes array segment
b[h..k-1]
to the following:

each element
i
,
h≤i<k
, should contain the sum of the original values of

b[h..i]
. Thus, if
b = {3, 5, 2, 7, 8}
initially, upon termination
b = {3, 8,

10, 17, 25}
. You should do this with one loop.

E11.
Rewrite selection sort of Sec. 8.5.4 to use this loop invariant:

0 ≤ j ≤ b.length
and
b[j..]
is sorted and
b[0..j-1] ≤ b[j..]

E12.
Another quadratic sorting algorithm is called
bubblesort
. It works as fol-

lows. First, array
b
is scanned beginning at b[0], swapping each adjacent pairs of

elements to put the larger of the two second. This “bubbles” the largest value to

the top —to
b[b.length-1]
. Next, start at
b[0]
and bubble the next largest to

b[b.length-2]
. Next, start at
b[0]
and bubble the next largest to
b[b.length-

2]
. Continue this process. Implement bubblesort.

E13.
Modify bubblesort of the previous exercise to stop as soon as one of the

bubbling-up processes does not swap any array elements.

E14.
Modify bubblesort of exercise E12 to alternate bubbling a larger value

upward and bubbling a smaller value downward, stopping when one upward or

downward pass does not swap any elements.

Search WWH ::

Custom Search