Lab: 23 - Mergesort

Assigned

Monday, 23 October 2023

Summary

Let’s practice with sorting algorithms.

Take a moment to view the Insertion Sort and Merge Sort interactive visualization programs written by David Galles at the University of San Francisco.

Getting Started

For today’s lab, we’ll take Weiss’s implementation of mergesort as a starting point. It can be found on MathLAN on lines 97–157 of the file /home/jimenezp/csc207/Lab-Sorting/Sort.java. To test your program you will need the file /home/jimenezp/csc207/Lab-Sorting/eight-cousins.txt.tokenized

Open up Eclipse and create a new Java project for this lab.

1. Create a new MergeSorter class, and copy the definitions (implementations) of the three methods that make up Weiss’s implementation of mergesort into your MergeSorter class file. The three before mentioned methods are:

    public static <AnyType extends Comparable<? super AnyType>>
    void mergeSort( AnyType [ ] a )
    private static <AnyType extends Comparable<? super AnyType>>
    void mergeSort( AnyType [ ] a, AnyType [ ] tmpArray, int left, int right)
    private static <AnyType extends Comparable<? super AnyType>>
    void merge( AnyType [ ] a, AnyType [ ] tmpArray, int leftPos, int rightPos, int rightEnd )
   

2. All three of these methods are declared using a type parameter between the keyword static and the return type void. What does this type parameter specify and how does it constrain the types of the elements of the arrays to which the first mergeSort method can be applied?
3. Why are the second and third of Weiss’s methods declared private rather than public?

Testing MergeSorter

Write and execute JUnit tests (one method per test) to determine whether Weiss’s mergeSort procedure correctly rearranges arrays.

• First, write the method isCorrectlyOrdered that takes an array of AnyType as its argument and determines whether its elements are correctly ordered.
  • Inside the isCorrectlyOrdered method, check the ordering of every two contiguous elements of the sorted array. They should be ordered such that arr[i] < arr[i + 1].
  • In order to use this array with generic methods, what type of elements must be in your array?
  • The header of this method uses the type parameter section as shown above. This indicates that the elements of the array must be Comparable together. Based on the description of the method, what should be the return type?
  • When the array is not ordered provide a message that includes the runtime class name of the object in your array (find the appropriate method in class Class).
• Then, write JUnit test methods.
  • Note that the isCorrectlyOrdered method accepts an array object as its parameter. Remember that you can find useful methods in the Java documentation for the List interface.
  • Test whether correctly rearranges an array that initially contains the values 24, 13, 26, 1, 2, 27, 38, and 15, in that order, so that at the end of the sorting process the elements of the array are in ascending numerical order.
  • For one of your tests, read the strings from the file eight-cousins.txt.tokenized and store them in a List. (This file contains the full text of Louisa May Alcott’s novel Eight Cousins, with one word or punctuation mark on a separate line.)
  • Explore the “Negative Space”, show that, given an array of zero or one elements, Weiss’s mergeSort method will return it unchanged, without ever invoking the merge method.

Comparable Switch

• The Switch class that we used in the “Lab 5: References and Objects” lab does not implement the Comparable interface, so we can’t use Weiss’s method to sort an array of Switch objects directly. Define a ComparableSwitch class that extends Switch, giving it a compareTo method that ensures that every switch that is turned off is ordered ahead of any switch that is turned on.

• Add JUnit methods to your tester class, test your code on a small array of 5 ComparableSwitch objects, set randomly to “on” or “off” (find the appropriate method in the Random class). Print your array before and after the sort so that you know if your code is working properly. Then write and execute a test that creates an array of ten thousand ComparableSwitch objects, randomly turns them on/off, calls mergeSort to sort them, and then checks to confirm that all of the “off” switches precede all of the “on” switches in the sorted array.

Lab Submission

You will submit your source files and the lab report (include the JUnit output) via Gradescope by the end of the week.

• (3 points) MergeSorterTester.java
• (1 point) ComparableSwitch.java

I strongly recommend that each student keep a copy of the lab. Therefore, don’t forget to share the files/folder with your lab partner!

Remember: Do not use magic numbers, write your code anticipating errors and print user-friendly error messages, all your public methods should be well documented (use Javadoc comments). Please include comments or organize your code and report in a way that will help the grader to find the answer to the exercises or posted questions.

Acknowledgements

From Data Structures & Problem Solving Using Java by Mark Allen Weiss