## CSC 300 Data Structures in Java I: Lab 3 (11/7 Thu)

In this lab session, you do an empirical test of performance comparison of various sorting algorithms.

You should be able to do Part I and II during the lab.  At the end of the lab (or before 11:59 pm 11/6 Fri), submit "MyBubble.java", which is described below.
Part III is optional.  If you have finished before the time, try Part III and have fun.

1. Download “Lab3.zip” from the course home page http://condor.depaul.edu/ntomuro/courses/300/, posted under “Week 8”. Save it under “My Documents” (but ensure the ‘Destination path’ is showing c:\Users\xxxx\Documents’)
2. Extract all files in the zip file under "My Documents" as well.

3. Start Eclipse. When you are asked to enter a workspace, browse to select Lab3 in the folder under "My Documents" (whose absolute folder is C:\Users\xxx\Documents\Lab3).
4. Now you create a new Java Project. From the top menu, select “File” and “New” and “Java Project”. Then in the pop-up window, type in algs4p for “Project name”. Then hit Finish.
5. Now for this lab, all files/classes should be added in the folder "algs21". It's under "algs4p" -> "src" in the left 'Package Explorer' pane in Eclipse. Click on the folder "algs21" and expand it.

### Part II: Writing MyBubble – the Bubble sort algorithm

• In the algs21 folder, you add a new Class MyBubble. In this class (“MyBubble.java”), you will write three methods:
1. public static void sort(int[] data) – This method receives an array of int’s, and sort the elements (in the ascending order). You can find the algorithm (Bubble sort) written in the lecture note (#8) Sorting Algorithms .
2. public static boolean isSorted (int[] data) – You know this method; same from the Take-home midterm.
3. public static void main(String[] args) – The main does some testing of the sort method.
• As for import libraries, you will need a few from java.util and possibly stdlib (if you useStdOut instead of System.out).  So the skeleton code will look like:
```package algs21;
import stdlib.*;
import java.util.*;

public class MyBubble
{
public static void sort(int[] data)
{
//
}

public static boolean isSorted(int[] data)
{
//
}

public static void main(String[] args)
{
//
}
}```
• The first two methods should be straight-forward. For main(), do the following.
• Declare an int array of size 10 (say ar1), and populate it with random int's (between 0 and 20).
• Print the content of the array by
`System.out.println(Arrays.toString(ar1));`
• Sort the array by calling the sort method with this array.
• Print the content of the array again (to see the visually verify the sorted result).
• Check the correctness of the sorting by calling isSorted() with the array, and display the result (sort result correct/incorrect).

• Create another int array of size 20 (say ar2), and populate it with random int's (between 0 and 40).
• Do the same steps above with this array.
• Below is the sample output
```=========================================
[19, 13, 6, 13, 4, 1, 0, 14, 12, 13]
[0, 1, 4, 6, 12, 13, 13, 13, 14, 19]
==> Correct.

===========================================================
[27, 13, 36, 11, 1, 18, 17, 27, 5, 17, 17, 18, 1, 3, 8, 1, 35, 37, 23, 32]
[1, 1, 1, 3, 5, 8, 11, 13, 17, 17, 17, 18, 18, 23, 27, 27, 32, 35, 36, 37]
==> Correct.```

### Part III: Comparing performance of sorting algorithms

• In the algs21 folder, you will see a file "CSC300Lab3Prog.java".  This file/class is complete (for now) and you can run it (provided you implemented MyBubble correctly).
Here is a sample output.
```N = 1000
(1) Insertion:      6,278,713
(2) Selection:     19,384,255
(3)    Bubble:      2,363,003
(4)  ArrayLib:        484,741```

It is showing the performance of four different sorting algorithms (Insertion, Selection, Bubble, and the one used in the Java Array library (which is called "Dual-Pivot Quicksort")).  The values are the execution time (in nanosecond, and averaged over 5 runs).

• Change main() so that you try various other sizes, in particular for larger sizes.  To wit, I recommend you double the size every time, for example, 1000, 2000, 4000, 8000 and so on.
• For each length, record the performance (execution time), and create a table (or a plot/graph). The main focus point is the rate of degradation (i.e., faster degradation means worse).
• On COL submission bin, type in your observation and comments. Your discussion should based on the understanding:
• Insertion, Selection and Bubble sort have the same average as well as the worst case complexity of O(n^2)..  But based on the empirical performance results, can you say (definitively/confidently) which algorithm(s) tend(s) to run faster in practice?
• The sort algorithm in Java's Arrays class seemed magnitudes faster than others.  The Java API for this function says:

"Implementation note: The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations. "

Do a search on the internet to find their exact algorithm, and present it (in the form of a document for me to read).

### Submission

Submit "MyBubble.java" on COL, Lab3 bin, before 11:59 pm 11/8 Fri.