Assignment № 7- Profiling the Bubble Sort Algorithm

In chapter #14 you were introduced to some sorting algorithms. In a supplementary handout,
we also discussed bubble sort, an elementary algorithm for sorting data. The algorithm has a
worst-case time complexity of O(n
2
). It has a best-case time complexity of O(n).
Definition 1. A sorting algorithm is said to be in-place when it executes without the need for
a large amount of secondary storage. The keys are usually overwritten and exchanged as the
algorithm executes.
Definition 2. A sorting algorithm is said to be stable when keys of equal values retain their
relative order during the execution of the algorithm.
Definition 3. An algorithm is said to be order-optimal if it has the best time complexity for that
class of problems.
Without any a priori knowledge of a data set that we can exploit, the most efficient a sorting
algorithm cam be is O (n log n). Although, bubble sort is not order-optimal, it is simple and can
be easily implemented as an in-place and stable algorithm. In spite of its relative poor worsecase performance, it does reasonably well with very tiny data sets and large data sets that are
partially or completely sorted. In this laboratory session, you will do an empirical analysis of the
performance of the algorithm using runtime as a metric.
The StopWatch Class
Use this class (see Big Java 8/e, pp. 633-634) to measure run times. This class is included
in the starter code archive file for this lab available for download on Moodle. Note that System.currentTimeMillis() returns the difference, measured in milliseconds, between the current
time and midnight, January 1, 1970 UTC. We can clock immediately prior to and after the execution of an algorithm. Subtracting the two times, we get an approximation of the execution time
of the algorithm. To express this execution time in seconds, we divide the time in milliseconds
(ms) by 1000.0.
The ArrayUtil Class
This class is also included in the starter code archive available for download on Moodle. The
original is from Big Java 8/e, pp. 630-631. I have made some modifications to the randomIntArray method so that it returns Integer[] rather than int[]. The random number generator in Java, as
Assignment № 7 Page 1
is the case in most languages, generates pseudorandom numbers. I have seeded the random
number generator using the time of day, a standard trick, as a parameter to its constructor so
that you don’t get the same pattern of random numbers across calls. I also tweaked the swap
method so that it exchanges two elements of Integer[] rather than int[]. You will also implement
the following methods:
1. public static Integer[] descIntArray(int length): returns an array of integers in descending
order - (length − 1),(length − 2), · · · , 1, 0.
2. public static Integer[] ascIntArray(int length): returns an array of integers in ascending
order - 0, 1, · · · ,(length − 2),(length − 1).
The Sorter Class
This class will contain your implementation for the bubble sort algorithm. It will contain only this
method:
public static void bubbleSort(Integer[] data)
This method sorts an array of integers in ascending order using the bubble sort algorithm described on the “Big-O Notation" handout on Moodle.
SorterDemo
Implement a class SorterDemo, the main class of the program. This class will consist of only
one method, the main method. Before you begin profiling the bubble sort algorithm, do the
following to test your implementation:
1. Generate an Integer array of length 100 with numbers in ascending order using the method
from the ArrayUtil class. Print the array.
(Use System.out.println(Arrays.toString(arrayReference);).
You will need to import java.util.Arrays.) Start the clock and sort the array using the bubbleSort method. Stop the clock. Print the array again. Also, print the time, in seconds,
that it took to sort the array. Subtract the start time from the stop time to obtain the time in
ms and then divide the result by 1000.0 to convert the time to seconds.
2. Repeat this for an array of length 100 with random integers. Call the relevant methods.
3. Repeat this for an array of length 100 with its integers in descending order. Call the relevant
methods.
This will give you some indication that everything works well so far! Delete the body of the main
method once you get it to work as described.
Rewrite the main method so that it generates arrays of various sizes and orderings as shown
in the table below. Your program should generate a table similar to the one shown in table 1.
(The question marks in the table represent run times in seconds. Display the run times to the
nearest hundred thousandths - five decimal places)
Assignment № 7 Page 2
Using Arrays of Integers With Different Orders
Sample Size (N) Ascending Random Descending
25000 ? ? ?
50000 ? ? ?
75000 ? ? ?
100000 ? ? ?
125000 ? ? ?
150000 ? ? ?
175000 ? ? ?
200000 ? ? ?
Table 1: Times To Sort Arrays Using Bubble Sort
Write your main method to manage memory efficiently. Retain only one data array in memory at a time. Reuse the same data array reference any time you need another array of a
different size or order. (You should not hold 24 data arrays in memory at the same time.)
Here is a suggestion on how you could structure your main method using a nested loop:
Listing 1: Suggested Code Structure
1 foreach (ASCENDING, RANDOM, DESCENDING)
2 {
3 foreach(SAMPLE SIZE)
4 {
5 case ASCENDING:
6 - generate array
7 - diplay a message for what is being done
8 - start clock
9 - call sort to sort array
10 - stop clock
11 - store time in execTimes[order][size] 2D array
12 case RANDOM:
13 ...
14 case DESCENDING:
15 ...
16 }
17 }
18 Print the table
This can be done in an elegant way by defining an enumerated type, Order, and a for or for each
loop to step through all the combinations. The table can then be generated using a nested loop
with printf statements using the relevant labels and format codes to get the columns aligned.
Assignment № 7 Page 3
Additional Requirements
Write header comments, where missing, for each class using the following Javadoc documentation:
/**
* Explain the purpose of this class; what it does <br
* CSC 1350 Lab # 7
* @author YOUR NAME
* @since DATE THE CLASS WAS WRITTEN
* @version 1
*/
For the Sorter class, after the @since line, add the following Javadoc:
* @see ArrayUtil
For the SorterDemo class, after the @since line, add the following Javadoc:
* @see ArrayUtil, Sorter, StopWatch
Add Javadoc style documentation for each method, where missing, except for the main method.
Run the Javadoc utility to make sure that it generates documentation for all classes and methods.
After your program runs, enter the data in the excel spreadsheet template provided along
with the starter code. Save the spreadsheet and then observe the chart/graph. Answer these
questions and save your responses in a text file called README.txt.
1. On which order of data was the bubble sort algorithm fastest? Why?
2. On which order of data did the algorithm perform worst?
3. What is the shape of the curve when the data set is already sorted (in ascending order)?
Random? Descending order?
4. For the same sample size, did the algorithm perform better on random data or data in
descending order? Why?
5. Did the empirical results, run times, generated by your program confirm the theoretical
results that we derived and discussed in class?
Locate your source files, ArrayUtil.java, StopWatch.java, Sorter.java and SorterDemo.java. Also,
locate the spreadsheet in which you have entered the run times that your program generated and the files containing responses to questions that you have been asked to answer,
README.txt. Enclose your source files, spreadsheet and README.txt files in a zip file, YOURPAWSID_lab07.zip, and submit your lab assignment for grading using the digital dropbox set up
for this purpose.
Assignment № 7 Page 4
Here is how the output of your program should appear. The ... denotes the run time in
seconds displayed to the nearest hundred thousandths (five decimal places).
Listing 2: Sample Run 1
1 Bubble Sort Run Times Using Arrays of Different Orders
2 ==============================================================
3 N ASCENDING RANDOM DESCENDING
4 25000 ... ... ...
5 50000 ... ... ...
6 75000 ... ... ...
7 100000 ... ... ...
8 125000 ... ... ...
9 150000 ... ... ...
10 175000 ... ... ...
11 200000 ... ... ...
12 --------------------------------------------------------------
Assignment № 7 Page 5