Java Reference
In-Depth Information
8.
Design a class called
BubbleSort
that is similar to the class
SelectionSort
given
in Display 6.11. The class
BubbleSort
will be used in the same way as the class
SelectionSort
, but it will use the bubble sort algorithm.
The bubble sort algorithm checks all adjacent pairs of elements in the array
from the beginning to the end and interchanges any two elements that are out
of order. This process is repeated until the array is sorted. The algorithm is as
follows:
Bubble Sort Algorithm to Sort an Array
a
Repeat the following until the array
a
is sorted:
for
(index = 0; index < a.length
−
1; index++)
if
(a[index] > a[index + 1])
Interchange the values of
a[index]
and
a[index + 1]
.
The bubble sort algorithm is good for sorting an array that is “almost
sorted.” It is not competitive with other sorting methods for most other
situations.
9.
Enhance the definition of the class
PartiallyFilledArray
(Display 6.5) in the
following way: When the user attempts to add one additional element and there
is no room in the array instance variable
a
, the user is allowed to add the ele-
ment. The object creates a second array that is twice the size of the array
a
, copies
values from the array
a
to the user's new array, makes this array (or more pre-
cisely its reference) the new value of
a
, and then adds the element to this new
larger array
a
. Hence, this new class should have no limit (other than the physical
size of the computer) to how many numbers it can hold. The instance variable
maxNumberOfElements
remains and the method
getMaxCapacity
is unchanged,
but these now refer to the currently allocated memory and not to an absolute
upper bound. Write a suitable test program.
10.
Write a program that will allow two users to play tic-tac-toe. The program
should ask for moves alternately from player X and player O. The program dis-
plays the game positions as follows:
123
456
789
The players enter their moves by entering the position number they wish to
mark. After each move, the program displays the changed board. A sample board
configuration is
XXO
456
O89
