CIS 180: Object-Oriented Programming

The application in this lab demonstrates two simple sorting algorithms (the Bubble and Selection sorts) and displays the data items in graphical form. When the application is started, random integer values are loaded into a data array. The data is displayed textually and graphically by the application. When the sort button is pressed, the data is sorted according to the currently selected algorithm, and the results are displayed.

If "Animated Selection" is chosen as the sorting algorithm, the process is animated: Pairs of numbers being compared are hilited in green, pairs of numbers being swapped are hilited in blue, and the sorted portion of the array is hilited in yellow. Pressing the reset button loads the array with a new set of random data.

Exercises

1. Compile and run the application. Try each of the sorting algorithms.
2. A good way to measure the efficiency of a sorting algorithm is to analyze the number of comparisons and swaps that it requires. Look carefully at the code for selection sort. For the array with 15 data elements, how many times is the comparison (a[j] < a[minPos]) made? How many times is the code to swap two elements executed?
3. Add variables to the selectionSort method to keep count of the number of comparisons and swaps that are made. Add code to print the totals to the java console (using System.out.println) just before the method returns. Compile and test your code. Was your answer to exercise 2 correct? What happens if you sort the array for a second time after it is already sorted, without resetting the array to random values?
4. Consider the bubble sort code. What can you say about the number of comparisons and swaps that will be made when you sort an array with 15 elements? How does this compare to selection sort?
5. Repeat exercise 3, this time modifying bubbleSort instead of selectionSort. Record your observations.
6. According to your tests, which algorithm appears to be more efficient in the majority of cases? What about the case when the array is already sorted?
7. Suppose that for a particular application (e.g. an address book), a large number of records are kept in a sorted array. After adding a few new records to the end of the array, it is resorted to restore the order. Which sorting algorithm would be more appropriate for this application? Why?
8. Modify selectionSort so that it produces an array sorted in descending instead of ascending order.