The goal of this project is to practice using recursion on a sophisticated algorithm.
As, usual, move into your cs235
directory,
clone the repository to make a directory for this assignment,
and change into it.
cd cs235 hg clone /cslab/class/csci235/proj4 cd proj4
What you'll find there are two files: the driver
Sort.java
from the last project and a new file
Merge.java
that contains the stubs for this project.
The final sort works this way: Suppose you have an unsorted pile of cards in your hand. First you split that pile up into two smaller piles. Then you sort each pile. Finally, you merge the two smaller (now sorted) piles into a full, sorted pile. This raises the question, how do we sort the smaller piles? The answers is-- the same way we sort the big one: we split those up each into two even smaller piles, sort those smaller piles, and merge them into a sorted small pile. We repeat the process (recursively) until we get to a pile of size 1, which is trivially sorted.
This sort is more efficient than the other three sorts in its use of time (ie, it's faster), but less efficient in its use of space, since this is not an "in-place" sort. It will use helper arrays to store some of the data temporarily.
We break down the task of writing this sort into a few manageable pieces-- each "piece" will involve writing a method. You should test these pieces individually by writing a main method for this file to test the individual methods. You will not be graded for the main method (in fact, you may delete it before turning the project in), but you will have an easier time with this if you test the pieces as you go. For example, the first piece is to write a method that will make an array from a portion of another array; you should test this by making an array, printing it out, calling the method you've written on that array, and printing out what the method returns.
Recall the String method substring()
.
Now we want to write a method that works similarly for
arrays.
Fill-in the body for the method subArray()
.
It should take an array, and starting index (inclusive),
and a stopping index (exclusive); it should create a new
array the size of the range specified (stop - start)
and copy the elements from the given array to the new array;
and return the new array.
After you have written this, document and test.
Next, we want to write a method that takes two
arrays---which it assumes to be already sorted---
and creates a new array, the size of the two given arrays combined---
and fills the new array with the elements from the two.
For example, given {2, 6, 8, 9}
and {3, 4, 5,
10}
, it should return an array {2, 3, 4, 5, 6, 8, 9,
10}
.
This is tricky. Think carefully about this, fill-in the body
of merge()
, and test.
Now, we want to implement the actual merge sort algorithm.
This will be in the body of mergeSort()
.
This method receives and array; it should
(1) split the array into two arrays representing its halves
(using subarray()
) (2) sort each half
(using mergeSort()
) recursively
(3) merge the result of each half together using
merge()
(4) return the result of merge()
.
The problem with what we have so far is that our driver
program expects the sort methods to be in-place sorts.
It just passes an array and expects the method to
mutate it.
We can simulate this by writing the sort()
method so that it (1)calls mergeSort()
on the given array, storing the result in another variable
(2) copying the elements from the result array back into
the given array.
Fill-in sort()
so that it works that way.
Create the script file as before (compile and run). Run each sort a couple of times.
Hand in your
Merge.java
and your typescript as project4
.
DUE: Mon, Oct 10, at 5:00 PM.