CSC349-Project 1: Empirical Analysis of Algorithms Solved

Goals of the assignment:   

Review algorithms learned in previous courses: selection sort, bubble sort, mergesort, quicksort.
Implement algorithms constructed by different strategies, using different techniques. Selection and bubble sorts are iterative algorithms while mergesort and quicksort both are recursive algorithms representing two great examples of divide-and-conquer strategy.
Analyze performance of implemented algorithms empirically, observing differences of their performances: selection and bubble sorts are O(N2) algorithms while mergesort and quicksort are O(NlogN) algorithms1. You will evaluate their performance based on their running time.
-----------

1   Reminder: quicksort’s worst case takes O(N2) time. However, with some effort the worst case is made exponentially unlikely which means that quicksort’s expected performance is as in its average case and thus it is classified as O(NlogN) algorithm.

PART 1:  I. Design and implement a class named Sorts

The Sorts class contains the implementation of 4 sorting algorithms and NOTHING else (the implementation of these algorithms must be consistent with the posted handout). This class does NOT have any instance or class variables, any constants (public or private), or any public methods except the ones stated below. Sorts class contains only four public methods for the four sorting routines plus all necessary private methods that support them. The four public methods are:

 

      public static  void  selectionSort (int[] arr, int N)

                 //Sorts the list of N elements contained in arr[0..N-1] using the selection sort algorithm.

 

      public static  void  bubbleSort (int[] arr, int N)

                 //Sorts the list of N elements contained in arr[0..N-1] using the improved bubble sort algorithm                  //(see the handout).

 

      public static void mergeSort (int[] arr, int N)   

                 //Sorts the list of N elements contained in arr[0..N-1] using the merge sort algorithm.

 

      public static void quickSort (int[] arr, int N)   

                 //Sorts the list of N elements contained in arr[0..N-1] using the quick sort algorithm with                   //median-of-three pivot and rearrangement of the three elements (see the handout).

Notes: 1. The list given as a parameter may not fill the arr array: it occupies arr’s 0 to N-1 cells.

No need for validity check – you can assume that arr.length >0 and N <= arr.lenght.
Attention: you may NOT change the names or signatures of specified four public methods; BE CAREFUL about the upper/lowercase letters in method names (misspelled name will make the grading program fail). You can define private methods as you see fit.

Design and implement an application class (or classes) to test your 4 sorting methods and make sure they work correctly. Run a lot of tests for each sort. 
PART 2: Design and implement an application class named SortTimes to generate the running times of Sorts class’ 4 routines. 

 

This class only needs a main method designed to run Sorts class’ public methods multiple times for different size lists and output the execution time in milliseconds for each method in each run.  

Attention:  1. To get the execution time of a method, you can capture the system time immediately before and immediately after the method call, and then take the difference. 

To obtain the system time, for more accuracy, use System class’ static method nanoTime() which returns the system time in nanoseconds as a long type value. To obtain the running time in milliseconds, you need to divide the obtained running time by 1,000,000. Note: time values should be represented as integer numbers.
 

Here is the description of steps that need to be done in main (variable N represents the number of elements in the list).

 

Define 4 arrays for 160,000 int type elements (the max size list you need to sort is 160,000). Notes: You need 4 copies of the original list: a sorting method alters the original list (sorts it), therefore you cannot use it as an input list for another method, hence the need for 4 copies of the original list. To hold 4 copies of the list, you need 4 arrays so you can pass different copies/arrays to different sorting methods. 
To test an algorithm on different size lists, it’s more efficient to have one array of max size (and fill it partially) rather than using a different N-size array for each N.
 

For different values of N (starting with 5,000 and doubling N’s value until 160,000 including), do the work defined below:
 Repeat the following steps 5 times (i.e. 5 times for each N-value): 

 

Create 4 copies of a list of N random integer values in the range [0, N-1], saving them in the first N cells of each of the four arrays (i.e. repeatedly select/generate a random number and save it under the same index in each of the four arrays).
Note: to obtain random integers, you can define a Random class object and call its nextInt  method. You can also use Math class’s random() method; in this case make sure to multiply the result by N and then cast it to an integer.  

 

Run each of the 4 methods of Sorts class (selectionSort, bubbleSort, mergeSort, and quickSort); make sure to give different arrays as a parameter for different sorts. Make arrangements to compute the execution time of each method (as described above). Output ONE line containing the value of N, followed by the execution times of all 4 sorts, separated by commas or spaces, in a descriptive sentence. For example, your output line may look like this:
 

                          N=value:  T_ss=time1,   T_bs=time2,   T_ms= time3,   T_qs= time4 

 

where value is the current value of N, and time1, time2, time3, time4 are the execution time values for selectionSort, bubbleSort, mergeSort, and quickSort correspondingly.

OUTPUT: the output produced by your SortTimes program should look something like this: 

 

                  Running Times of four sorting algorithms: 

 

N=5000:  T_ss=time1,   T_bs=time2,   T_ms=time3,   T_qs= time4

N=5000:  T_ss=time1,   T_bs=time2,   T_ms=time3,   T_qs= time4 N=5000:  T_ss=time1,   T_bs=time2,   T_ms=time3,   T_qs= time4 N=5000:  T_ss=time1,   T_bs=time2,   T_ms=time3,   T_qs= time4

N=5000:  T_ss=time1,   T_bs=time2,   T_ms=time3,   T_qs= time4

 

N=10000:  T_ss=time1,   T_bs=time2,   T_ms=time3,   T_qs= time4

N=10000:  T_ss=time1,   T_bs=time2,   T_ms=time3,   T_qs= time4

N=10000:  T_ss=time1,   T_bs=time2,   T_ms=time3,   T_qs= time4

N=10000:  T_ss=time1,   T_bs=time2,   T_ms=time3,   T_qs= time4

N=10000:  T_ss=time1,   T_bs=time2,   T_ms=time3,   T_qs= time4

 

N=20000:  T_ss=time1,   T_bs=time2,   T_ms=time3,   T_qs= time4

N=20000:  T_ss=time1,   T_bs=time2,   T_ms=time3,   T_qs= time4

N=20000:  T_ss=time1,   T_bs=time2,   T_ms=time3,   T_qs= time4

N=20000:  T_ss=time1,   T_bs=time2,   T_ms=time3,   T_qs= time4

N=20000:  T_ss=time1,   T_bs=time2,   T_ms=time3,   T_qs= time4

          

N=40000:  T_ss=time1,   T_bs=time2,   T_ms=time3,   T_qs= time4

N=40000:  T_ss=time1,   T_bs=time2,   T_ms=time3,   T_qs= time4

N=40000:  T_ss=time1,   T_bs=time2,   T_ms=time3,   T_qs= time4

N=40000:  T_ss=time1,   T_bs=time2,   T_ms=time3,   T_qs= time4

N=40000:  T_ss=time1,   T_bs=time2,   T_ms=time3,   T_qs= time4

 

N=80000:  T_ss=time1,   T_bs=time2,   T_ms=time3,   T_qs= time4

N=80000:  T_ss=time1,   T_bs=time2,   T_ms=time3,   T_qs= time4 N=80000:  T_ss=time1,   T_bs=time2,   T_ms=time3,   T_qs= time4

N=80000:  T_ss=time1,   T_bs=time2,   T_ms=time3,   T_qs= time4

N=80000:  T_ss=time1,   T_bs=time2,   T_ms=time3,   T_qs= time4

 

N=160000:  T_ss=time1,   T_bs=time2,   T_ms=time3,   T_qs= time4

N=160000:  T_ss=time1,   T_bs=time2,   T_ms=time3,   T_qs= time4

N=160000:  T_ss=time1,   T_bs=time2,   T_ms=time3,   T_qs= time4

N=160000:  T_ss=time1,   T_bs=time2,   T_ms=time3,   T_qs= time4

N=160000:  T_ss=time1,   T_bs=time2,   T_ms=time3,   T_qs= time4

 

                  End of output 

       

Note: of course instead of all time1, time2, time3, time4 terms you’ll have actual integer numbers:

 

Attention: Your output should be EASY TO READ; e.g. print a blank line at the end of each iteration of the N-loop (as shown in the above example).

IMPORTANT!  

ANALYZE YOUR OUTPUT THOROUGHLY. Make sure that your output reflects the expected behavior for each algorithm. Remember that selection and bubble sorts are expected to execute in O(N2) time while mergesort and quicksort are expected to do the job in O(NlogN) time. You should notice that (i) the bubble sort is noticeably slower than the selection sort due to the large number of swaps it has to do at each iteration, and (ii) the mergesort is noticeably slower than the quicksort due to the fact that at each step of recursion it uses a temporary array for merging the two sorted halves of the list-segment.

Prepare a text file called txt containing the output produced by SortTimes program. You will need to submit this file together with your program. You can get your output in a file if you run the program on the command line and direct your output to the mentioned file:
   javac SortTimes.java    java  SortTimes  > times.txt