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