COMP553 PRACTICAL EXERCISE 3 - BUBBLE SORT

1. REQUIREMENTS

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:

1. 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.
2. 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 setv (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.

Note: There already exists a LINIX command sort so do not call your class "sort"!

2. REPORT

You should hand in a report of the (by now) standard format comprising the following sections:

1. Requirements: (outline of the above)
2. Analysis: A short description of your analysis of the problem including a Class Diagram.
3. Design: Detailed descritions for the methods you intend to include.
4. Implementation: A computer print out of your implementation.
5. Testing: A set of appropriate Black box and White box test cases together with results and evidence of data validation.

3. MARK SCHEME

Marks will be awarded for:

1. Analysis and Design (25%)
2. Implementation (50%)
3. Testing (25%)

Remember the guidance notes on the presentation of work. Marks distributed evenly over analysis, design, implementation and testing.

Created and maintained by Frans Coenen. Last updated 14 November 2001