← back to the schedule


MINI-LAB #5
Sorting Algorithms



In this mini-lab you will use several implementations of sorting algorithms and answer the questions below. Please download sorters.zip, a file containing all the algorithms needed. Please review the code in these files:

  • Sorters.java contains code implementing all the sorters you will need (and more): Two implementations of Bubble Sort, Insertion Sort, Selection Sort, Merge Sort, and Quick Sort, as well as Bogo Sort (a.k.a. Stupid sort), Radix Sort, and Counting Sort
  • Tester.java contains tests, creates several lists to be sorted, and a "pretty printing" method that generates CSV files (comma separated values) that you can use to plot the time your tests take.


Stage 1

Test 1: Using the Tester.java file, create a test for the 2 Bubble Sort algorithm implementation bubbleSort1() and bubbleSort2(). Make a plot with your resulting csv file. Make sure to invoke the printCSV() method with the following paramaters: (allDurations, 2, "test1.csv")

Test 2: Perform the same test as above, but now instead of passing a unsorted list to each of the methods, sort the list first using the following statement: Collections.sort(list), and then pass it to the corresponding Bubble Sorts. Make sure to invoke the printCSV() method with the following paramaters: (allDurations, 2, "test2.csv")

Test 3: Using the Tester.java file, create a test for the 3 algorithms with O(n2): Bubble Sort, Insertion Sort, and Selection Sort. Since there are two implementations of Bubble Sort, use bubbleSort2(). Make a plot with your resulting csv file. Make sure to invoke the printCSV() method with the following paramaters: (allDurations, 3, "test3.csv")

Test 4: Perform the same test as above, but now instead of passing a unsorted list to each of the methods, sort the list first using the following statement: Collections.sort(list), and then pass it to the corresponding sorters. Make a plot with your resulting csv file. Make sure to invoke the printCSV() method with the following paramaters: (allDurations, 3, "test4.csv")

In your document answer the following questions:

  1. Does the original ordering of the elements in the lists impact the number of comparisons made by both implementations of Bubble Sort in Test 1 and Test 2?
  2. What can you say about the behavior of Insertion Sort in Test 3 with respect to Test 4?
  3. What can you say about the behavior of Selection Sort in Test 3 with respect to Test 4?
  4. Include the figures obtained from Test 3 and Test 4


Stage 2

Answer the following general questions about sorting algorithms:

  1. Each of the sorting algorithms that we have discussed (selection, insertion, bubble, merge, and quick) have their own strengths and weaknesses. Is any one of these algorithms the best choice under all circumstances? Can you think of a scenario for each sorting algorithm in which it would be the best choice?
  2. A stable sort is defined as a sorting algorithm that preserves the original order of duplicate elements. Which of the sorting algorithms that we studied are stable sorts?
  3. Can you implement merge sort without recursion? Explain your answer. Why is the time complexity of a merge sort always O(n log2 n)?
  4. Java implements a sorting algorithm in the Collections class: Collections.sort(List list). Which of the sorting algorithms in underlying the implementation of this sort() method? What’s its time complexity?
  5. Radix sort can theoretically sort a list in O(n) or linear time. Why isn’t this sorting algorithm the best of them all? Can you explain its caveats?

Submit your completed answers through Kit, under Mini-Lab 5.

EVALUATION

Mini-lab #5 is worth 15 points. This mini-lab will be submitted individually. Prepare a document with your answers and submit to Kit in PDF format. If you decided to append timing results between the sorting algorithms, or if you generated plots from it to show how the algorithms behave as the list increases in size, you can append them to your document as well.

Have fun! And if you have any questions remember my email, my office hours, and the collaboration center are here for you!



← back to the schedule