MergeSort: In class we saw the mergesort sorting algorithm. Look at the Java implementation that was posted to the notes part of the course webpage (found here).
In this implementation, we create many new arrays (and copy a lot of values to these new arrays) during the algorithm. One of the reasons for implementing it this way is that when the sorting is completed, we have a new array that has the same values as the original array, but in sorted order. One important aspect of this, is that the original array is left unchanged ( we call this a non-destructive function).
In this problem, you will investigate the efficiency costs of using this non-destructive mergesort versus a destructive version (where the original input array is changed).
Remember that in Java, when we pass a parameter into a function/method, we simply make a local copy of that parameter in the function/method. For primitive types, we get a real copy of the actual data. For everything else, arrays and objects, we get a local copy of the pointer to where the actual array or object lives in memory.
We can exploit this in a new mergesort as follows: First, instead of creating a new array (perhaps consisting of the first half of the original array) and passing a pointer to this new array recursively to the mergesort function, we can simply pass our pointer to the original array along with some additional information to tell us which part of the array we should look at. Second, we will make our changes (when merging) directly to the original array.
Your new mergesort function should look like
public static void mergeSort2(int[] M, int start, int end){..}
where start and end specify the portion of the array
that you want to sort. The function will then sort
the elements of the array M from index start up to, but not including end.
The function will change the data that the input parameter M points to.
We say that the function mutates the input array M.
So,
MergeSort2.mergesort2(A, 0, A.length); // sorts the entire array A MergeSort2.mergesort2(A, 0, A.length/2); // sorts the first 1/2 of A
For this problem, create a class called MergeSort2
that has new versions of the merge and mergesort functions.
Both of these functions should mutate the input array(s) and
return nothing. This class cannot have a main() function.
Also create a class called CompareMerge,
that compares the efficiency (run time) of the MergeSort
implementation and your MergeSort2 implementation.
This class should time many runs of both methods (where
the same array is being sorted by each method in each run).
Your main() function for this class should display
some useful information, such as average runtimes for
different size input arrays; ranges of input sizes where
one method is better than the other; or the same; or worse, etc.
Submit your MergeSort2.java file and
your CompareMerge.java file (in your assignment zip file).
IntList: In this problem, you will create recursive methods based on the following recursive definition of a list of integers:
A list of integers is
o) a single integer
(which we'll call the "first" of the list),
and another list of integers
(which we'll call the "rest" of the list)
or it is
o) empty
Create a class called IntList, to implement a list
of integers with the following attributes and methods:
// attributes private int first; private IntList rest; // methods public int getFirst(); // Purpose: returns the first integer in the list // (does not change the list) // Precondition: there must be at least one number in the list public IntList getRest(); // Purpose: returns the rest of the list // (does not change the list) // Precondition: there must at least one number in the list public void add(int item) // Purpose: add an integer to the (front) of the list // item becomes the new first number in the list // the entire list before adding becomes the rest // of the list // (the list is changed by this method) public int remove() // Purpose: returns the first number in the list // removes this number from the list // (the list is changed by this method) // Precondition: there must be at last one number in the list // constructor public IntList(int x, IntList rest)
This should seem very familiar to you. It is essentially a stack that is implemented with a linked list of nodes.
Add the following recursive methods to your class:
public void print() // Purpose: displays the contents (the numbers) of the list // from first to last // (the list is not changed by this method) public void printReverse() // Purpose: displays the contents (the numbers) of the list // from the last to the first // (the list is not changed by this method) // Note: this method should be VERY similar to your print() public boolean isIn(int x) // Purpose: returns true of x is an integer in the list // returns false if x is not in the list public int whereIs(int x) // Purpose: returns the "index" of where the first instance of // x is in the list. Here, index starts with 1 (not zero) // If x is not in the list, returns 0 public boolean remove(int x) // Purpose: removes the first instance of x in the list // returns true of x was initially in the list // returns false if x was not in the list // (and hence, could not be removed)
Do not include a main() function in IntList.
Submit your
IntList.java file for this problem (in your
assignment zip file).
Testing:
Create a class called TestIntList. Using the function
specifications from the IntList class (from above), write
three black-box test cases for each method (not including the
constructor).
Your main() method should simply run each of your tests and output if you passed or failed the test. Your output (to the screen) should look something like:
Testing getFirst(): pass pass pass Testing getRest(): pass fail fail ...where you list the method you are testing, then (on the same line) indicate if you passed or failed your test.
We will take your testing class and test our own IntList implementations with bugs embedded into it. Your testing should find bugs in our code.
Submit your
TestIntList.java file for this problem (in your
assignment zip file).