CSCI241 Assignment 1

CSCI241 Assignment 1

1 Overview
In this assignment, you will implement four sorting algorithms, an interactive command-line
program that demonstrates the sorting algorithms, and create a write-up analyzing the number
of comparisons performed by each sort as a function of input array size.
Your primary tasks are as follows:
• Implement the methods for insertion, merge, quick, and radix sorts in Sorts.java. You
will also need to implement the merge and partition helper methods for merge sort and
quick sort, respectively.
• Implement the user-facing behavior described below in SortsDriver, using the sorting
methods from Sorts.java to perform the sorting.
• Create a writeup analyzing how number of comparisons grows as a function of input array
size for insertion, merge, and quicksort.
• The base assignment is worth 45 points; to earn the remaining 5 points (or more, for extra
credit), you can complete some of the enhancements described in Section 6 (or come up
with your own) and explain what you did in your writeup.
2 Getting Started
The Github Classroom invitation link for this assignment is in Assignment 1 on Canvas. Begin
by accepting the invitation and cloning a local working copy of your repository as you did in
Lab 1. Make sure to clone it somewhere outside your lab1 working copy (e.g., ~/csci241/a1)
1
to avoid nesting local repositories. Skeleton code is provided in your repository to get you
started.
See Section 7 below for a suggested game plan for getting the sorts, user interface, and
writeup done. The following sections provide details and hints on each subtask.
3 Sorting Algorithms
Sorts.java contains method headers for six public methods:
• insertionSort
• merge
• mergeSort
• partition
• quickSort
• radixSort
The method headers and specifications (i.e., the name, return type, parameters, and the
Javadoc comment specifying the method’s behavior should not be changed. If you change
method names, call signatures, or return values, your code will not compile with the testing
system and you’ll receive no credit for the correctness portion of your grade.
Public methods must implement their specifications precisely and completely. For example,
even if your quickSort method always calls partition using the first element as the pivot,
partition is still required to work with any other legal pivot index specified, because such
behavior is prescribed in the specification.
In Lab 2, you will write unit testing code that will help you check the correctness of the
sorting methods. As you develop the sorts, you should run gradle test frequently and make
sure that each algorithm passes all its tests before moving on to the next.
3.1 Implementation Notes
• You may write and use as many private helper methods as you need.
• The mergeSort and quickSort implementations must be recursive and all sorts must be
asymptotically efficient.
• The Sorts class has a private member comparisonCount. In each of the sorts that you
implement, use this counter to tally the count of comparisons that are done between
entries of the array as it is sorted. For example, for insertionSort, tally the number of
times that array[j] < inputArr[j-1] is performed. For quickSort, tally the number
of times that A[j] is compared to the pivot, etc. Be sure to count all comparisons made,
not just those that evaluate to true. You do not need to count comparisons among loop
variables (e.g., you should ignore the i < n comparison in a for loop header).
• The bottom of Sorts.java has two private helper methods written for you that you may
find useful.
2
• Radix sort requires the use of a stable sorting algorithm to sort the array on each digit.
You can either use counting sort (see CLRS 8.2) or maintain a list of queues, one to store
the contents of each bucket. Counting sort is algorithmically trickier. On the other hand,
creating an array of queues of integers in Java can be a bit painful because of the way
generics and arrays interact. The following snippet creates and populates an ArrayList
of 10 buckets, each of which is a LinkedList of integers:
ArrayList<LinkedList<Integer>> buckets = new ArrayList<LinkedList<Integer>>(10);
for (int i = 0; i < 10; i++) {
buckets.add(new LinkedList<Integer>());
}
Because buckets is an ArrayList, use buckets.get(i) to get the LinkedList storing the
i’th digit. Remember that a LinkedList implements the Queue interface; see the Java
documentation for details on which methods make it behave like a Queue.
• Radix sort as described in class does not naturally play well with negative integers. Get it
working on nonnegative numbers first, then figure out how to handle negatives. You may
assume that the values to be sorted are not extremely large or small and do not approach
the largest or smallest value that can be represented using an int.
4 Interactive Program Behavior
The main method of SortsDriver should implement a program that behaves as follows. To run
the program, you can simply use gradle run. When the program starts, it should:
1. Prompt the user for the size of the array, n, and create an array of that size made up of
integer values chosen randomly from -n..n+1.
2. Prompt the user to specify which sort to use (merge sort, quick sort, insertion sort, radix
sort, or all). The user should be asked to enter a single letter: m, q, i and r, or a.
3. If all (a) sorts is specified, the input to each sort must be identical
4. If n ≤ 20, the pre-sorted and sorted array’s contents are printed for each sort invoked
5. If n > 20, the pre-sorted and sorted array’s contents are NOT printed for each sort invoked
6. The count of comparisons performed is/are output.
Several sample invocations of the program are shown in Figure 1. Note the order of the
prompts must be as specified, though the text does not need to be precisely the same as the
example.
4.1 Implementation Notes
• Error catching is NOT required. You do not have to catch if a user specifies a negative
count of entries, or inputs a letter, or provides a sort option that is not m, i, q, r nor all.
Consider using a switch statement.
• The java.util.Random and java.util.Scanner classes from the Java Standard Library
may come in handy.
3
% java SortsDriver
Enter sort (i[nsertion], q[uick], m[erge], r[adix], a[ll]): q
Enter n (size of array to sort): 15
Unsorted: [ -12 5 -9 15 -7 13 9 13 10 -7 14 -14 -14 2 -10 ]
Sorted: [ -14 -14 -12 -10 -9 -7 -7 2 5 9 10 13 13 14 15 ]
Comparisons: 42
% java SortsDriver
Enter sort (i[nsertion], q[uick], m[erge], r[adix], a[ll]): m
Enter n (size of array to sort): 1000
Comparisons: 8709
% java SortsDriver
Enter sort (i[nsertion], q[uick], m[erge], r[adix], a[ll]): r
Enter n (size of array to sort): 12
Unsorted: [ 4 1 -8 5 -2 12 -7 -4 -11 -7 -5 -8 ]
Sorted: [ -11 -8 -8 -7 -7 -5 -4 -2 1 4 5 12 ]
Comparisons: 0
% java SortsDriver
Enter sort (i[nsertion], q[uick], m[erge], r[adix], a[ll]): a
Enter n (size of array to sort): 10
Unsorted: [ -9 9 -6 -8 -4 0 -7 -3 6 8 ]
insertion: 13
Sorted: [ -9 -8 -7 -6 -4 -3 0 6 8 9 ]
quick: 21
Sorted: [ -9 -8 -7 -6 -4 -3 0 6 8 9 ]
merge: 23
Sorted: [ -9 -8 -7 -6 -4 -3 0 6 8 9 ]
% java SortsDriver
Enter sort (i[nsertion], q[uick], m[erge], r[adix], a[ll]): a
Enter n (size of array to sort): 1000
insertion: 248189
quick: 10453
merge: 8695
Figure 1: Sample Invocations of SortDriver.java
4
• Do not use System.console to read user input.
• Do not create more than one Scanner object reading from System.in. Re-use the same
Scanner object for all user input.
• To ensure that the all option works as intended, you’ll need to make a deep copy of the
randomly generated array to give to each sort method.
• For the all option, avoid counting comparisons for multiple sorts: either reset the comparison counter (there’s a handy method for this provided in Sorts.java) or create a fresh
Sorts object for each sort.
• Precise comparison counts may differ based on subtle implementation choices, even across
multiple correct solutions. However, the relative counts between insertion sort O(n
2
) and
quick sort O(n log2 n), for example, should differ greatly and clearly demonstrate their
relative run-times.
• As described in the style guide on the syllabus and the rubric at the end of this document,
overly long methods (e.g., with hundreds of lines of code) are considered bad programming
style. Be sure that your program is broken down into sensible, modular helper methods,
rather than a monolithic main method.
5 Writeup
Your writeup should include the following:
• Table. For the insertion, quick, and merge sorts, run each of them on successively larger
arrays, and tally the count of comparisons made as a function of n, the array size. Vary
n from 10 to 500 and list the data in a table. See Figure 2 as an example. Notice that
radix sort is not listed here; you be able to explain why this is the case.
n Insertion Quick Merge
10 33 21 24
50 607 234 222
100 2459 550 528
200 11353 1401 1282
500 58535 4682 3852
Figure 2: Sample tally table
• Plot. Using graphing software of your choice, create a plot of the values you have tallied.
Be sure to label both the x and y axes, provide a title, and make sure that you provide a
legend to make it easy to identify merge, insertion, and quick sort performance. A sample
plot is shown in Figure 3.
• Discussion. Describe any design decisions you made along the way. If you complete any
of the enhancements (see below), describe what you did and include any associated plots
or analysis.
• Acknowledgements If applicable, list any people you collaborated with and any external
resources (i.e., anything other than the recommended texts, lecture slides, and help in
office hours) you used in the course of completing this assignment
5
Figure 3: Sample plot of comparisons done by insertion, merge, and quicksort
6 Enhancements
The base assignment is worth 45/50 points. The final 5 points may be earned by completing
one or more of the following enhancements. You may also come up with your own ideas - you
may want to run them by the instructor to make sure they’re worthwhile and will result in
points awarded if successfully completed. It is highly recommended that you complete the base
assignment before attempting any enhancements.
Enhancements and git The base project will be graded based on the master branch of
your repository. Before you change your code in the process of completing enhancements, create
a new branch in your repository (e.g., git checkout -b enhancements). Keep all changes
related to enhancements on this branch—this way you can add functionality, without affecting
your score on the base project. For example, the first enhancement asks you to add a third
user prompt to choose between a sorted array and a random array. As this departs from the
user-facing behavior described in the base project, such a change should only be made in your
enhancements branch. Make sure you’ve pushed both master and enhancements branches to
GitHub before the submission deadline.
1. (1 point) Real-world sorting inputs rarely come in uniformly random order. Add a prompt
that allows the user to choose among the following arrays that try to model some likely
real-world use cases:
• A random array (as in the base project)
• A fully sorted array
• An array that is sorted, except the last 5% of its values are random
• An array in which 90% of elements are, amongst themselves, in sorted order, while the
other 10% are random. Tip: the java.util.Random class’s nextDouble() method
generates a random floating-point value between 0.0 and 1.0.
Generate another plot for each of these types of arrays. Describe the differences—which
ones can you explain? Are any surprising/inexplicable?
2. (2 points) Make a table and plot of performance in terms of elapsed time instead of
number of comparisons. You may find the built-in System.nanoTime() function useful.
3. (2 points) Implement the median-of-three (first, middle, last) pivot in quicksort. Plot the
number of comparisons done by both variants of quickSort and insertionSort. (1 additional
6
point) Repeat this experiment, but run the sorts on sorted arrays and nearly-sorted arrays
from Enhancement 1.
4. (Up to 4 points) Most real-world sorts built into modern programming languages are
hybrid algorithms that combine more than one algorithm depending on the array size,
ordering, etc. Implement a hybrid sorting algorithm and analyze its performance relative
to the other sorts. You may find it interesting to note differences in performance measured
by number of comparisons vs elapsed time. Try to outperform both quicksort and insertionsort on random, sorted, and mostly-sorted arrays. You may search the internet for
inspiration and strategies, but please cite your sources, write your own code, and explain
your algorithm in the writeup. A good-faith attempt that does not beat insertion and
quicksort may still receive some credit.
7 Game Plan
Start small, test incrementally, and git commit often. Please keep track of the number of hours
you spend on this assignment; when you are finished, write the approximate number of hours
you spent as a lone integer in hours.txt and make sure it is included when you push your final
changes to github to submit. Hours spent will not affect your grade.
A suggested approach is outlined below:
1. Implement the insertionSort method in Sorts.java. Use the skeleton code provided
for you in SortsDriver.java test out the insertionSort method to sort on a small fixed
array. When you have this working, commit your changes to git.
2. In SortsDriver, implement and test random array generation. Prompt the user for array
size and which sort, and add functionality to print the array before and after sorting.
3. Implement each of the remaining sorts, testing using both the driver and the unit tests
as you go. Commit your changes git frequently, and push to github each time you get a
new piece working. Recommended order: merge, quick, radix.
4. Implement the all option. Avoid copy/pasting code you’ve already written—instead,
factor useful pieces into private methods that you can call more than once. Commit your
changes.
5. Create the table and plot in your writeup. Don’t forget axis labels, legend, and title.
6. If you plan to do any enhancements, create an enhancements branch in your repository
to track the changes beyond the base project (git checkout -b enhancements). Commit all new changes to this branch and don’t merge it into the master branch. Add a
description and analysis of each enhancement to your writeup.
7. Fill in hours.txt, run the tests one last time, and read through the rubric to make sure
you’ve finished everything. Read through the code clarity section to be sure you won’t
lose style points; see the syllabus for more details on coding style.
Rubric
For the coding portion of each assignment, you earn points for the correctness and efficiency of
your program. Points can be deducted for errors in commenting, style, clarity, etc.
Hours
Code is pushed to github and hours spent appear as a lone integer in hours.txt 1 point
Writeup
Tally table of comparison counts for quicksort, merge sort, and insertion sort. 3
Plot of tallied numbers, including axis labels, title, and legend. 3
Code : Correctness
Sorting algorithms and helper methods are implemented correctly as determined
by unit tests (1 point per test).
20
Program prompts user for number of integers desired, relies on random number
generator to populate the array, and prompts for type of sort to run (m, i, q, and
r, a).
3
Each invocation of a sort correctly tallies the count of comparisons made. 3
When the a option is specified, all four sorts are invoked, whose input is the
same array.
2
If n ≤ 20, pre-sorted and sorted array(s) are printed; otherwise, the arrays are
not printed.
2
Code : Efficiency
Mergesort runs in O(n log n) 2
QuickSort runs in O(n log n) in the expected case 2
Insertion sort runs in-place, and runs O(n
2
). 2
Radix makes a constant number of O(n) passes over the input. 2
Enhancements
See Enhancements section above. up to 5
Clarity deductions (up to 2 points each)
Include author, date and purpose in a comment comment at the top of each file
you write any code in
Methods you introduce should be accompanied by a precise specification
Non-obvious code sections should be explained in comments
Indentation should be consistent
Method should be written as concisely and clearly as possible
Methods should not be too long - use private helper methods
Code should not be cryptic and terse
Variable and function names should be informative
Total 50 points
9