CS 261 Lab L - Merge Sort

Due Wed Apr 30 at 9:00am

Overview

For this lab, you will practice implementing a sorting algorithm from scratch, based just on the description of the algorithm. Moreover, you will be integrating this sorting algorithm with an existing program--a program that you wrote before!

That's right: you'll be modifying the card flipping lab from way back when to allow the user to shuffle and sort the deck of cards! Furthermore, you'll add a simple "animation" to the sorting, so that you can more easily see it in action.

The particular sorting algorithm you will be implementing is called Merge Sort. This is a recursive sort--that is, we use recursion to do the sorting! This makes it both simple to describe but possibly tricky to implement (in the same way that recursion is always tricky).

Don't worry, we will go over the algorithm together during lab before you get started!

This lab will be completed in pairs. Remember to review the pair programming guidelines before you get started!

Objectives

To practice implementing a sorting algorithm from a description
To learn about Merge Sort
To explore and practice with methods from the Arrays and Collections utility classes
To once again practice modifying and working with a (mostly) existing program, particularly with GUI-based programming!

Necessary Files

You will need to download the copy of the SortingCardLab.zip file. and import the included classes into Eclipse. As before, this zip file contains a Card class that is the basis for a playing card, a DrawableCard class that represents a card that can be drawn, a DrawableDeck class to organize all the cards, and a basic CardFrame class to display the deck.

You will need to make one small change to the DrawableCard class and fill in a number of methods in the DrawableDeck class. Other functionality has been provided for you.
Remember to also add the "assets" folder to your Eclipse project, so that you can load in the card faces.

Merge Sort

Merge Sort is a fast sorting algorithm. It is described in detail (with sample code!) on page 441 of the textbook. A description can also be found on Wikipedia. And of course, we will go over the algorithm in lab together.

The basic premise is that if we have two smaller lists (A and B) that are already sorted, then it becomes very easy to combine them together into a single sorted list. You simply compare the smallest item from A and the smallest item from B, and then put that item in your final sorted C list (removing it from A or B as appropriate). Repeat this process until you've added all the items from A and B to C.

But how can we convert an unsorted list into a pair of sorted lists to then merge? We'll first split the list in half, and then sort each half--and we'll sort each half using a merge sort! This is the recursive step--each of those halves get split in half, sorted, and then remerged... we know that we can stop splitting in half when our list has only a single element; this single item is already sorted, so no more recursive is required!

Merge Sort is thus implemented using two methods: the recursive mergeSort() and the helper merge(), which can be described with the following pseudocode:

void mergeSort(originalList):
  if originalList has more than 1 element
    leftList = copy left half of the original list into a new list
    rightList = copy right half of the original list into a new list
    mergeSort(leftList)
    mergeSort(rightList)
    merge(leftList, rightList, original)

void merge(left, right, output):
  while not finished with either list
    compare the front items in both lists
    copy the smaller into the output list
    access the next item from the list who you copied from
  while more elements in left
    copy elements form left into the output list
  while more elements in right
    copy elements fom right into the output list

The actual "sorting" occurs in the merge step; the mergeSort step simply breaks the list down so we know what to merge!

Note that this algorithm is generally not performed "in-place"--that is, you sort items into a new list, which you then make replace your original. We'll be addressing that problem in our implementation.

Again, we will go over this in a bit more detail in lab, and an example implementation can be found in the text.

Assignment Details

There are a number of small pieces to this assignment, described below:

1. Make Cards sortable

The first thing you'll need to do is to make it so we can sort the playing cards! This means they will need to be Comparable. This process should be simple enough--we've done this kind of thing before!

You should sort by suit then by rank, with Aces coming last.
Pro Tip: if you can come up with a numerical representation of each card, with "earlier" cards having smaller numbers then you can easily fill in the compareTo() method simply by subtracting the numerical values. What happens if you use the suit as the "hundreds" place and the rank as the "tens and ones" places?

2. Add Shuffle functionality

You'll also need to be able to shuffle the cards so that you can then sort them! Fill in the provided shuffle() method in DrawnDeck.

There are a number of shuffling algorithms (which are basically reverse sort algorithms): for example, you might do a kind of "selection sort", but select a random element to swap with instead of the smallest element.
An easier way to add a quick shuffling feature would be to use the built-in Collections.shuffle() method, which takes in a List to shuffle (this is the same method we've been using during lecture). Simply call this method on your list, and it's shuffled!
- Of course, this method requires a List... and the Cards are stored in an array. So you'd need to copy the array elements into a list, shuffle the list, and then copy the items back into the array.
- An easier way to do this (I know!) would be to use the Arrays.asList() method, which can be used to easily turn an array into a list! And once the list is shuffled, you can use the .toArray() method of the List class to convert it back into an array. Note that this method requires a new array of size 0 passed as a parameter, so Java knows what type to convert it to! (Again, see the lecture code for an example).

The moral of the story: Java has lots of utility classes that can help you do common tasks quickly, if you know where to look. This lab is intended to help you find where to look!

3. Implement Merge Sort

Now that the preliminaries are out of the way, on to the main event: implementing the merge sort algorithm. Fill in the provided sort() method in DrawnDeck (important note: this method will act as the launcher for your recursive call; you will need to make separate helper methods!)

As described above, the merge sort algorithm has two parts:

mergeSort()
This method normally takes in a list to sort, splits that list in half, recursively sorts each half and then calls merge() to combine them back together in place of the original list.
- However, in this program we're interested in doing the sorting as "in place" as possible (so that it can show up in the correct spot of the display). So instead of creating copies of the list to sort, you'll want to specify a section of the original deck to sort. You can do this by indicating the "start" index for the section and the "length" of that section. So the section that starts at index 4 and has a length 3 represents the elements at indices {4,5,6}.
  
  Your mergeSort() method should thus have the following signature:
```
private void mergeSort(int start, int length)
```
- You can calculate the "midpoint" of the list by dividing the length in two (and offsetting by the start!), and then calculate the start and lengths of the two sublists ("left" and "right")
- But in order to actually merge the sublists, you'll need to copy the elements into new arrays of the appropriate length. You can do this easily using a for loop, but you might look at the Arrays.copyOfRange() method as a easy way to do this!
  - By assigning these new arrays to the left and right instance variables, you'll be able to see what sub-arrays are being merged when you add in animation (step 4). This is the one time it's okay to use instance variables with recursive methods.
  - Pass these arrays to the merge() method, described below.
merge()
This method takes in two lists to merge, and places the combined items in order into some "output" list.
- For this program, the "output" list will be the original deck array!
- But you'll need to know where to start outputting into the original array (since we might only be mergeing two lists of size 1, that go somewhere in the middle). So you'll want to take in a parameter that says at what index the merging of these subarrays will start--the index of the "leftmost" element of the "left" subarray!
  
  Your merge() method should thus have the following signature:
```
private void(DrawnCard[] left, DrawnCard[] right, int start)
```
  Again, the parameter you pass to this method from mergeSort() will be the index of the leftmost item of your left subarray--so the "start" value of the left subarray!
- Otherwise, the merge method is pretty straightforward (and is detailed in the textbook). You'll be using 3 while loops (not nested):
  1. The first loops through the two subarrays until one is out of elements. It compares the "front" item of each subarray, and puts the smaller item into the output array (in this case, the deck)
  2. The second loops through the first subarray (usually left), adding the remaining items (if any!) in that subarray to the output array.
  3. The third loops through the second subarray (usually right), adding the remainign items (if any!) in that subarray to the output array. Note that only one of these two loops actually ends up DOING anything, but we include both anyway!
- The best way to handle these loops and keep track of where you are in the subarrays is to use index variables (e.g., leftIndex, rightIndex, deckIndex), which get incremented whenever you move to the "next" spot.

Once you have these methods implemented, you should be able to shuffle and then resort your list!

4. Animate the Sorting

Finally, once you have sorting working, you can add periodic "pauses" in order to slow down the algorithm and see how it works. There are a couple of steps to this:

The DrawnDeck class contains a provided wait() method that you can use to put small "pauses" into your algorithm. This method should look familiar from the Fractal homework, and it is used in a similar way. Note that I have provided a handy WAIT_TIME_MILLIS constant for you to use, to help avoid magic numbers!
- I recommend putting a pause after every "swap"--that is, everyone one of your lists changes (when merging).
Make sure that your subarrays are copied into the left and right instance variables, so that they show up in the frame!
The merging algorithm doesn't actually "move" cards; instead it just replaces the cards in main deck with the ordered cards from the subarrays. This means that you might see the same card appear in multiple places in the deck, as well as in the subarray.
- The fix for this is to "remove" the card from the main deck after you copy it into a subarray. You can do this by replacing the element at that card's index with null. So after you copy a bunch of items into the left or right subarrays, replace those items in the deck with null!
  - You can do this with a for loop, but wouldn't you bet there's a handy method inside the Arrays class that might do this for you? Take a look at the Arrays.fill() method.
- Similarly, after you place a card back into the deck from one of the subarrays, null out the item in the subarray so it disappears!
  - It's a good idea to put a pause after you do this.

And that should do it! You should now be able to see your deck sort itelf via merging!

Extensions

One extension you can add if there's time is to "highlight" the cards that are currently being compared and moved. You can do this by marking the particular cards as selected (just like you did with the original flipping lab!) It is possible to earn up to 5 pts of extra credit for adding this extension.

However, since you will be comparing multiple cards, you'll need to have multiple selections (rather than a single selected index). You could make a list of selections... but you should consider making a HashSet of selections! This is a Set (why is that appropriate?), and because it is built on a hash, it gives constant time access--it is very fast to check if a particular card is selected or not!
- You will need to add and remove selected cards from this set at appropriate times--think about when the "current" selected card changes. Be sure and pause afterwards so we can see the selection!
If a card is selected, you can use a provided alternative Card.draw() method that takes in an additional boolean parameter--representing whether the card should be drawn as selected or not. You'll need to modify the paintComponent() method.

You might also consider adding different sorting algorithms (that also animate in a similar fashion). Be sure and add more buttons to the CardFrame so you can test different sorts! You can earn another 5 pts extra credit for this extension

This is actually a really good study aid for the sorting algorithms, and a way to literally "see" them all in action!

Submitting

Make sure your name is in a class comment at the top of all the classes you modified and upload them to the LabL submission folder on vhedwig. Make sure you upload your work to the correct folder! The lab is due at the start of class on the day after the lab.

After you have submitted your solution, log onto Moodle and submit the Lab L Partner Evaluation. Both partners need to submit evaluations.

Grading

This assignment will be graded based on approximately the following criteria:

Cards are comparable [10%]
A working shuffle method [20%]
A working mergesort implementation [50%]
Sorting is animated [15%]
You completed your lab partner evaluation [5%]