CS171 (Spring 2012)

Assignment 5: Advanced Sorting Algorithms

Assigned: Wednesday, March 22

Due: Wednesday, March 28, 11:59pm

 

Goals:

1. Implement a non-recursive version of mergesort for primitive data types.

2. Compare the average running times of quicksort and mergesort algorithms with bubble sort on inputs of different sizes (and plot the running time as a chart).

 

Details:

1. Non-Recursive Merge Sort

The starter code contains a method called nonrecMergeSort() with the following header:

 

   public static void nonrecMergeSort(long[] a);

 

You must fill in this method with code that implements a non-recursive version of merge sort.  You may call the merge() method that is already implemented in the starter code to accomplish merging. The merge() method is implemented slightly differently from the book version.  You need to allocate a workspace array (similar to the auxiliary array used in the book) in order to call this merge() method. In addition, you need to correctly calculate the low, middle, and upper indices and pass them as arguments to the merge() method. Alternatively, you may implement your own version of the merge() method if you wish.

 

We will assume that the size of the input is always a power of 2. This reduces the complexity of the solution. If your implementation is correct, it should in fact run slightly faster than the recursive mergesort, because there is no recursive call overhead.

 

Similar to Hw2, in the starter code, we use a testSort() method to check whether your implementation sorts correctly. This method compares your sorting result with reference result. It returns true if both results are completely the same, and false otherwise. If your sorting result is wrong, the program will print out a message 'The sorting is INCORRECT!!!!!!' at various points.  At the very beginning of the main() method, we inserted three lines of code to help you test your implementation using a small array of size 64. This can make debugging easier. Note that your merge sort should work for array of any size, not just 64.

 

2. Comparing Sorting Algorithms

In the second part, you will compare the average performance of 4 different sorting algorithms: bubble sort, recursive merge sort, non-recursive merge sort, and quicksort. The non-recursive mergesort is what you've implemented in part 1; the other three are provided in the starter code and do not need further changes.  Note that they provide a slightly different but similar implementation with the implementations on the book.

 

The code for reporting the runtimes is initially commented out in the main() method. When you are done with part 1 above, you can remove the two lines marked by 'remove this line'. This section of code will perform several rounds of tests for each of four sorting algorithms. For each algorithm, it tests 15 different input sizes (the first 15 powers of 2), and the input data are randomly generated. It performs each test 5 times in order to get an average running time. Afterward, the code will print out a table: each row of the table reports the input size (N), and the average running time for each of the four tested algorithms. The times reported are in milliseconds. Familiarize yourself with the code in the main method and make sure you understand how the experiments are being carried out. Run the main method and examine the table to compare the run times for the algorithms. You can increase the value of the max variable, but be aware that the sort may take quite a bit of time, so be prepared to wait.

  

After the program prints out the table, plot the results in graphs, similar to Hw2.

 

Bonus:

Include the selection sort and insertion sort implementation from hw2 in the comparison.  You will need to modify the main method to correctly run the experiment for each of the 6 algorithms, print out the result table, and plot the results.

 

Starter Code:

Starter code is provided to you in Sorting.java. Bubble sort, recursive merge sort, and quicksort have been implemented for you. You must fill in the nonrecMergeSort() method. Other than this, you shouldn't need to make modifications to any other parts of the code, except for removing the two lines in the main() method, as explained above.

 

Getting started:

1.    Download the starter code and make sure you understand everything in the starter code.

2.    Fill in the honor code

3.    Complete the method nonrecMergeSort(), which should implement a non-recursive version of mergesort.

4.    Check the output of the first three lines of the main() method to make sure your non-recursive mergesort is correct.

5.    Remove the two lines marked "remove this line". Run the program, wait for a bit for the output.

6.    If it takes too long, try to reduce the value assigned to the max variable (it's currently set to 14).

7.    Plot the performance chart using instructions in hw2.

 

Honor code

The assignment is governed by the College Honor Code and Departmental Policy. Please remember to have the following comment included at the top of the file.

 

      /*

      THIS CODE IS MY OWN WORK, IT WAS WRITTEN WITHOUT CONSULTING

      CODE WRITTEN BY OTHER STUDENTS. _Your_Name_Here_

      */

 

Submission:

Your completed Sorting.java and Sorting.png (or Sorting.jpg, etc. depending on your image type) should be placed in your ~/cs171/hw5 directory which will be collected for grading.

 

Grading:        

·         Correctness and robustness: your non-recursive mergesort sorts correctly for any input array (that has a size of power of 2). (60 pts)

·         Efficiency: your non-recursive mergesort is efficient, and the running time is less than the recursive mergesort in most cases when N>512 (20 pts).

·         Code clarity and style (5 pts)

·         Correctness of the plot: you included a running time chart and the data is correctly plotted. (15 pts)

·         Bonus (5 pts)

 

Enjoy!