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.
VideoNote
Solution to
Programming
Project 6.8
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 element.
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 precisely 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 com-
puter) 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 displays the
game positions as follows:
1 2 3
4 5 6
7 8 9
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 con-
figuration is
X X O
4 5 6
O 8 9
