|
CSE 1030 - Assignment #8 - A Recursive Implementation of Merge Sort
SC/CSE 1030 - Fall 2012 - Assignment #8
A Recursive Implementation of Merge Sort
The Merge Sort algorithm was invented by John von Neumann in 1945.
Merge Sort is an important algorithm because it is very efficient at sorting data that
can only be accessed serially (for example, data stored in a linked-list).
Your task for this assignment is to code a recursive implementation of
Merge Sort. The merge sort algorithm sorts data by breaking the input into
two lists, which are then sorted (by calling merge sort recursively),
and which are then merged back together in order. The process is described
by the following diagram:
There are three parts to a typical merge sort implementation, (1) a procedure
that splits the input into two lists, (2) a function that merges two
ordered linked-lists together, and (3) the merge sort algorithm as described
in the figure above. For this assignment you will have to implement two
of the three parts of the merge sort: the merge algorithm, and the main
merge sort algorithm.
In practical terms this means that you will have to write two functions,
public static Node merge(Node p, Node q), and,
public static Node mergesort(Node head).
A skeleton program, Mergesort.java,
that contains the rest of the implementation has been provided for you.
To complete this assignment you must complete the implementation
of merge sort provided in the Mergesort.java file. To do this you
will have to:
Implement the required two functions, matching the
details in their respective comments in the skeleton program:
public static Node merge(Node p, Node q), and,
public static Node mergesort(Node head).
Include appropriate comments in your source code.
You should test your implementation using the main()
function provided in the skeleton program.
You should also test your implementation using the a8.java
tester program.
Submit your program electronically before the deadline
using the submit command:
submit 1030 a8 Mergesort.java
Some notes:
A skeleton program implementing some of the merge sort functionality
has been provided for you here:
Mergesort.java.
Note that two places in the skeleton program have been marked with comments,
indicating where you need to add code in order to complete this assignment.
(You shouldn't need to change or add code anywhere else in the skeleton
program.)
Implement your linked lists manually, using the Node class defined in the
skeleton program. Do not use any of the Java Collections to complete
this assignment (i.e., no LinkedList<Node>, nor Queue<Node>, etc.)
You must implement the merge sort algorithm yourself;
you may not use any of the search functionality provided by the Java API
(i.e., no java.util.Collections.sort(), and no java.util.arrays.sort()
etc.).
You will find the following useful for testing your code:
a8.java.
This program provides a simple command-line interface to
several tests to help you test your code.
Your source code should be well organised and documented.
Remember the Course's, Department's, and the University's
policies on academic honesty - do your own assignment yourself.
(Besides, doing it yourself is the only way to learn!)
This assignment is due on Friday November 23, at noon. Late
assignments will not be accepted.
Start Early - Don't leave your assignment to the last minute!
Remember that you can use the submit command more
than once - subsequent submissions will replace previous
submissions. So if you make a mistake, don't panic,
just fix it, and resubmit it (before the deadline).
Additional information regarding the submit command can be
found by typing man submit at the command line.
Do not use the Type package, nor its earlier
incarnation, the york package.
Your programs must compile and run on the Prism computers.
Your grade will be a number from 0 to 10 (vaguely reflecting the tests in the a8.java tester program). The breakdown is:
3 marks for a correctly functioning public static Node merge(Node p, Node q) function.
6 marks for a correctly functioning public static Node mergesort(Node head) function.
1 mark for coding style (nicely organised code with comments).
Have FUN!
|
|
