Sorting is a frequent operation. A one dimensional (1-D) array can be
sorted if there is an ordering relation between the elements in the
array. For example if the array comprises a set of integer elements we
can order the elements according to the integer number line. A common
method whereby the elements in a 1-D array may be sorted is called the
bubble sort. Assuming an array of positive integers which we wish to
sort according to the sequence represented by the integer number line,
the bubble sort operates as follows:
Find the two adjacent elements, X and Y, in the array such that X > Y
and swap X and Y, then sort the resulting array.
If there is no adjacent pair of elements, X and Y, in the array such
that X > Y, the list is "sorted".
Note that the purpose of swapping two elements X and Y that occur out
of order is so that after the swap the new list is closer to a sorted
list. After a sufficient amount of swapping we should end up with all
the elements in order. For example given the array:
{1 2 5 4 7 3 6 8 10 9}
we would commence by finding the elements 5 and 4 and swap them to
get:
{1 2 4 5 7 3 6 8 10 9}
We would then continue as follows:
{1 2 4 5 7 3 6 8 10 9}
{1 2 4 5 3 7 6 8 10 9}
{1 2 4 3 5 7 6 8 10 9}
{1 2 3 4 5 7 6 8 10 9}
{1 2 3 4 5 6 7 8 10 9}
{1 2 3 4 5 6 7 8 9 10}
The process is known as a bubble sort because elements slowly "bubble
up" to their correct location.
Design and implement a Java program which sorts a 10 element integer
array using the bubble sort process. The elements of the array to be
sorted should be supplied by the user and should not include any
duplicates. Hint: refer to earlier array examples (Metres to Yards,
Feet and Inches conversion, Set I/O and Set intersection) for guidance
on how to process arrays.
Please try to include comments in the code. |
