Assignment 2: Sorting
COMP 2140, Fall 2021
Due: Tuesday 19 October 2021 at 5:00 p.m
Instructions
You must complete the “Honesty Declaration” checklist on the course website before you can submit
any assignment.
Assignments must follow the programming standards document published on UM Learn.
After the due date and time, assignments may be submitted, but will be subject to a late penalty. Please
see the course outline document published on UM Learn for the course policy for late submissions.
If you make multiple submissions, only the most recent version (the last submission) will be marked.
We strongly encourage you to submit early!
These assignments are your chance to learn the material for the exams. Code your assignments inde-
pendently. We use software to compare all submitted assignments to each other, and pursue academic
dishonesty vigorously.
You can get help from the T.A. during your lab section and from the instructors and from the course
Assignment 2 discussion forum on UM Learn. You can discuss general topics related to the assignment
with fellow students or other people, but you cannot discuss the solution to the assignment with them.
You cannot copy code from anywhere except COMP 2140 class notes, unless we tell you otherwise. For a
full discussion of our expectations for individual work on this assignment, see the Department of Compute
Science’s expectations webpage.
Your Java programs must compile and run upon download, without requiring any modifica-
tions.The marker will not fix your program’s problems.
This assignment is a combination of written and programming questions. You need to submit both .java
and .pdf files.
See also the “Hand in” instructions at the end of this assignment
Assignment Overview
As we saw in the class, Merge Sort divides an input suba
ay in to two suba
ays of equal sizes, recursively sorts
the two suba
ays, and then merges the two suba
ays. In this assignment, you are asked to implement and
test “AltMergeSort”, which is an alternative Merge Sort algorithm that divides the a
ay into four suba
ays
of equal sizes, recursively sorts each of them, and then merges the four sorted suba
ays. In particular, fo
sorting the suba
ay starting at index lo and ending at index hi, we define n = hi - lo + 1, and then mid1
= blo + n/4 − 1c, mid2 = blo + 2 ∗ n/4 − 1c, and mid3 = blo + 3 ∗ n/4 − 1c. The algorithm recursively sorts
suba
ays in ranges [lo, mid1], [mid1+1, mid2], [mid2+1, mid3], and [mid3+1, hi] and then merges the
sorted suba
ays.
For example, consider the following suba
ay, with lo = 12 and hi = 27, and n = 16. The value of mid1 is
lo + n/4− 1c = 15. Similarly, we have mid2 = blo + 2n/4− 1c = 19, and mid3 = blo + 3n/4− 1c = 23.
1
https:
sci.umanitoba.ca/cs/expectations
The algorithm starts by recursively sorting the three suba
ays. The base of recursion is as we saw in the
class, that is, when lo ≥ hi, there is nothing to do (any suba
ay of one element is already sorted). After sorting
the four suba
ays, the above a
ay looks like this:
After the recursive calls, the algorithm merges the four sorted suba
ays. The merging process is simila
to the one we saw in the class. The only difference is that we have four indices (named a, b, c, and d) that
iterate over the four suba
ays. Initially, we have a = lo, b = mid1+1, c = mid2+1, and d = mid3+1. At each
iteration, the smallest suba
ay value stored in one of positions a, b, c, or d is copied to the next available index
k in a temp a
ay. In the above example, at the first iteration, a
ay[lo], a
ay[mid1+1], a
ay[mid2+1], and
a
ay[mid3+1] are compared and, since the content of a
ay[mid1+1] is the smallest, it is copied to temp[lo]
(and then k and b are incremented). The following figure shows the state of the algorithm at the end of the fifth
iteration:
Assignment Questions
Programming part:
Create a file named A2
your first name>.java (e.g., A2CameronHelen.java) to contain
your code. (Make sure the class it contains matches the file name.)
Then add the following methods to your code (when applicable, you can use the same methods you used in
Assignment 1):
1. A method fillA
ay, which is passed an int a
ay and a maximum value (an int). It should fill the
given int a
ay with random positive integers no larger than the given maximum value.
Hint: (int)(Math.random() * maxValue) produces a random integer in the range 0, . . ., maxValue-1.
2. A method a
ayToString that is passed an int a
ay and returns a String containing the first 10, followed
y “. . . ”, followed by the last 10 items in the a
ay (or just all the items in the a
ay if the a
ay’s length
is 20 or less). The items should be separated by blanks.
2
3. A method isSorted that verifies that an a
ay is in ascending order. It should be passed an int a
ay. It
should return true if the a
ay is in ascending sorted order and false if it is not. It must check that each
item in the a
ay is no bigger than the item immediately after it.
4. A method to merge four sorted suba
ays. Its signature is:
private static void merge ( int[] a
ay, int lo, int mid1, int mid2, int mid3, int hi ,
int[] temp )
The method should merge four sorted suba
ays a
ay[lo..mid1], a
ay[mid1+1, mid2], a
ay[mid2+1,
mid3], and then a
ay[mid3+1, hi] as described above.
Hint: You must pay attention to the ending indices of the suba
ays. For example, if index a becomes
mid1 + 1, a
ay[a] should not be copied to temp.
5. A method mergeSortAlt to sort an a
ay of integers as described above (using four recursive calls). In
addition to sorting the a
ay, the method is supposed to return the height of the recursion subtree.
Recall that the height of the recursion tree indicates the maximum depth of recursion, that is, the maximal
number of nested recursive calls. In the base of recursion, when there is at most one item in the suba
ay,
the height of the recursion tree is 0. One way to find the height of the recursive function is to find the
height for each of the four recursive calls, take the largest among them, and add 1 to it.
The signature for mergeSortAlt is as follows:
public static int mergeSortAlt (int [] a
ay)
Note that this method is the public driver method for the sort. You must implement the private, recursive
helper method.
Hint: In order to check the co
ectness of the output height, you can calculate the height of the tree on
paper. Think of the following question: what is the height of the tree as a function of n? (you can start
with n = 16 and then extend to the larger values of n).
Finally, write a main method (and whatever helper methods it needs) to do all of the following for each of
the iterative and the recursive insertion sorts:
Create an a
ay of 10000 random positive integers no greater than 5000.
Print the the first 10 and the last 10 items in the a
ay (before sorting).
Sort the a
ay and time the sorting. (Copy the code that times a method from the Lab1.java file.)
Check if the a
ay is co
ectly sorted, and print either “A
ay is co
ectly sorted” or “ERROR: A
ay is
NOT co
ectly sorted” (as appropriate).
Print the height of the recursion tree.
Print the the first 10 and the last 10 items in the a
ay (after sorting).
Then add to your file the iterative insertion sort described in the class.
Finally, the main method should report the timings and also which of the two methods was faster.
Sample Output:
Assignment 2 Solution (merging with four recursive calls)
Testing the iterative insertion sort:
A
ay before sorting:
XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX4337
3
A
ay is co
ectly sorted
A
ay after sorting:
XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX
Testing the alternative merge sort:
A
ay before sorting:
XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX3094
A
ay is co
ectly sorted
A
ay after sorting:
XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX
The height of the recursion tree is: 7
Timing:
Time to insertion sort: XXXXXXXXXXnanoseconds
Time to alternative merge sort (recursively): XXXXXXXXXXnanoseconds
The alternative merge sort was faster than the insertion sort!
Processing ends
Written part:
Draw the recursion tree for an input formed by n = 17 integers. At each node of the tree, indicate the values of
lo and hi associated with the recursive call. You need to complete the following figure.
You can draw the tree on paper and take pictures of it or use a computer application. In any case, you
should convert your drawing into a .pdf file.
Hand In
To submit the assignment, upload the specified files to the Assignment 2 folder on the course website.
Verify that the submission worked. (See the detailed hand-in instructions in the “COMP2140-HandIn-
Instructions” document under “General Information” in the content
owser of the course website on
UM Learn.)
Submit ONE .java file, which must be named A2
your first name>.java (e.g.,
A2CameronHelen.java) and one .pdf file, which must be named A2
your first name>.pdf
(e.g., A2CameronHelen.pdf).
Do not submit .class or .java~ files (or compressed files or directories)!
The marker will not edit your .java file in any way, so make sure it will compile and run for the marker.
Make sure your .java file does not specify a package at the top!
4