Project # 3 Sorting Algorithms

Learning Objectives
• Empirical Comparative Analysis of Various Sorting Algorithms
• Studying The Effects of Ordered versus Unordered Data On Various
Sorting Algorithms
In this project, you will build on work began in laboratory exercise # 7.
First, you will generate arrays containing random integer arrays using the
ArrayUtil.randomInt method with the sizes shown in table 1. For a given
size, generate one array, then copy the array and apply the algorithm to the
copy. At any given point, you should have only two arrays in memory - the
original and its copy. You may find the Arrays.copyOf method in the Java
API handy when copying arrays.
You will run the algorithms on each copy and measure the runtimes. Your
program should generate table 1. (The question marks in the table represent
runtimes in milliseconds.)
Arrays With Random Integers
n Selection Insertion Bubble Quick Merge
10000 ? ? ? ? ?
20000 ? ? ? ? ?
30000 ? ? ? ? ?
40000 ? ? ? ? ?
50000 ? ? ? ? ?
60000 ? ? ? ? ?
Table 1: Time To Sort Arrays
Then, you will generate arrays of the same sizes but these array will contain
sorted integers. Your program should also generate a table similar to the one
shown in table 2 and table 3 using the relevant methods of the ArrayUtil
class.

Sorting Algorithms CSc 1351: Programming Project # 3
Arrays With Integers in Ascending Order
n Selection Insertion Bubble Quick Merge
10000 ? ? ? ? ?
20000 ? ? ? ? ?
30000 ? ? ? ? ?
40000 ? ? ? ? ?
50000 ? ? ? ? ?
60000 ? ? ? ? ?
Table 2: Time To Sort Arrays
Arrays With Integers in Descending Order
n Selection Insertion Bubble Quick Merge
10000 ? ? ? ? ?
20000 ? ? ? ? ?
30000 ? ? ? ? ?
40000 ? ? ? ? ?
50000 ? ? ? ? ?
60000 ? ? ? ? ?
Table 3: Time To Sort Arrays
The Sorter Class
In addition to the bubble sort method that was implemented in lab # 7,
this class will contain four additional static methods. The code for these
algorithms are in chapter 14 of the textbook but you will tweak them so that
they take long[] rather than int[] as an explicit parameter. The Sorter class
will contain the following methods.
public static void selectionSort(long[] data)
private static int minimumPosition(long[] data, int from)
public static void insertionSort(long[] data)
public static void bubbleSort(long[] data)
public static void quickSort(long[] data)
private static void quickSort(long[], int from, int to)
private static int partition(long[] data, int from, int to)
public static void mergeSort(long[] a)
private static void merge(long[] first, long[] second, long[] data)

Sorting Algorithms CSc 1351: Programming Project # 3
The mergeSort and quickSort methods are recursive methods and have auxiliary methods. In each case tweak the methods to work with Integer objects
rather than int.
The SorterDemo Class
Listing 1: Suggested Pseudocode for Random Arrays
1 for arraySize := 10000 to 60000 StepSize :=10000
2 {
3 data := generate random array of size arraySize
4 foreach { INSERTION , SELECTION , BUBBLE , QUICK , ←-
MERGE }
5 {
6 dataCopy := copy the data array
7 case INSERTION :
8 reset clock
9 start clock
10 perform insertion sort
11 stop clock
12 runTimes [ arraySizeIndex ][ INSERTION ] = ←-
elapsed time
13 case SELECTION :
14 reset clock
15 start clock
16 perform selection sort
17 stop clock
18 runTimes [ arraySizeIndex ][ SELECTION ] = ←-
elapsed time
19 case BUBBLE :
20 ...
21 case QUICK :
22 ...
23 case MERGE :
24 ...
25 }
26 }
27 print Table

Sorting Algorithms CSc 1351: Programming Project # 3
Write a client program called SorterDemo to measure the run times and
generate the tables described above. You may find the pseudocode in Listing
1 helpful in generating the first table with arrays containing random integers.
You may similarly measure run times for sorting arrays in ascending and
descending orders.
Plotting Your Data
Using MicroSoft Excel and the template workbook given to you, generate
graphs showing the results in the three tables that your program generated.
The workbook has five additional tables and plots:
1. Sorting Algorithms vs Random Data
2. Sorting Algorithms vs Ascending Order Data
3. Sorting Algorithms vs Descending Order Data
4. Selection Sort vs Various Data Orders
5. Insertion Sort vs Various Data Orders
6. Bubble Sort vs Various Data Orders
7. Quick Sort vs Various Data Orders
8. Merge Sort vs Various Data Orders
You only need to enter data in the first three sheets in the workbook and
your entry will be copied to the remaining five sheets and the plots will be
updated automatically.
Analysis
Include a file, README.txt, in which you describe your observations about
how the various algorithms performed when given data sorted in ascending
and descending orders and random data. For each algorithm, discuss whether
it performed better, worse or more or less the same. Then say which algorithm(s) perform best for a given initial ordering of the data. You may either

Sorting Algorithms CSc 1351: Programming Project # 3
use the tables your program generated or the graphs you plotted to do this
analysis. Conclude with a general observation about how these algorithms
perform and conditions under which you will use a given algorithm. Your
analysis should not exceed 1-page.
Additional Requirements
Write header comments for each class using the following Javadoc documentation template:
/**
* Explain the purpose of this class; what it does <br
* CSC 1351 Project # 3
* @author YOUR NAME
* @since DATE THE CLASS WAS WRITTEN
*/
For the SorterDemo class, after the @since line, add the following Javadoc:
* @see Sorter, StopWatch, ArrayUtil
For the Sorter class, after the @since line, add the following Javadoc:
* @see ArrayUtil
Add Javadoc documentation for the Sorter class and each of its methods.
Also, add Javadoc header comments for the SorterDemo class. Run the
Javadoc utility to make sure that it generates documentation for the ArrayUtil, StopWatch, Sorter and SorterDemo classes. Also, remove all autogenerated Netbeans comments. Locate your source files, ArrayUtil.java,
StopWatch.java, Sorter.java and SorterDemo.java , and the MicroSoft Excel
Worksheet, results.xls and README.txt. Enclose them in a zip file, YOURPAWSID proj03.zip, and submit your programming project for grading using
the digital dropbox set up for this purpose.