Lab 11: Merge Sort and Quick Sort

Introduction

In this week’s lab, you’ll implement two of the sorting algorithms that we learned about in lecture this week. Sorting is an incredibly interesting, prevalent, and satisfying branch of algorithm design. In lecture, we focused on sorting arrays. In this lab, you’ll instead focus on sorting linked lists, which requires some cleverness and a good understanding of how merge sort and quick sort operate.

All of the functions that you write will operate on the Princeton Queue Implementation, which implements a queue using a linked list. You should familiarize yourself with the API linked above, as you will use the public methods of the Queue class to implement these sorting algorithms.

Merge Sort

Test Driven Development

In this week’s lab, you’ll practice test-driven development (TDD) by having a test be the first piece of code you write. With test-driven development, you start by writing a test that fails (because you haven’t written anything else yet!). After writing the relevant code, you re-run the test to make sure that it passes.

Today, you’ll begin by writing a JUnit test in the provided TestSortAlgs.java file. Your test should first create a Queue of unsorted objects. Next, call MergeSort.mergeSort() on that queue, and assert that it is sorted (you can do this by checking each element is greater-than-or-equal to the element before it).

You can put any kind of object you like in your test queue, as long as the object implements the Comparable interface. It may work well to create a Queue of Strings, as in the code below:

Queue<String> tas = new Queue<String>();
tas.enqueue("Joe");
tas.enqueue("Omar");
tas.enqueue("Itai");

Try running your test. Is the output what you expect, based on the implementation we provided of mergeSort()?

Sorting

If you need to review how mergesort works, you may find the Merge sort demo from lecture or this Merge sort demo to be useful. As well, here is a quick visual demo:

merge sort

To help you implement merge sort, start by implementing two helper methods:

Once you’ve finished implementing these helper methods, use them to implement mergeSort. With the help of the two methods above, your mergeSort method should be short (fewer than 15 lines of code). Run the main method you wrote above to test whether your mergeSort implementation works!

Quick Sort

Test driven development

As you did for merge sort, begin by writing a JUnit test. You can put this in the same file in which you wrote your other test, or make a brand new one. Once again, create an unsorted Queue, sorts it, and assert it is sorted. As always, try to think about what corner cases you may run into when performing quick sort.

Sorting

If you need to review how quick sort works, take a look at slides 6 through 10 from this lecture. You’ll be using the 3-way merge partitioning process described on slide 10. There is still a Hungarian dance demo for quick sort, however the dancers decided to use a different partitioning scheme we will not cover, known as Lomuto Partitioning. Finally, here is perhaps a less intuitive but more mesmerizing visual demo:

quick sort

Begin by implementing the helper function partition(). The partition() method takes an unsorted queue called unsorted and an item to pivot on, and three empty queues called less, equal, and greater. When it returns, less should contain all items from unsorted that were less than the pivot, equal should contain all items from unsorted that were equal to the pivot, and greater should contain all items that were greater than the pivot.

Once you’ve implemented partition(), use it to implement the quickSort function. You may find the getRandomItem() and catenate() methods that we’ve provided to be useful. Using these helper functions, your quickSort method should be short (fewer than 15 lines of code).

TA Overview

At the end of lab, your TA will go over the reference solution to MergeSort and Quicksort. This will be helpful if you haven’t finished the lab, since we don’t want you to be stuck working on lab too much outside of lab. (This is also an incentive for you to go to lab!)

Submission and Recap

In this lab we covered the implementation of Merge Sort and Quick Sort on the Queue ADT. You already know the drill, but just to remind you, make sure to push your code to GitHub and submit to Gradescope to get credit for this lab. We will only be grading the code you have written in MergeSort and QuickSort.

FAQ

What does the <Item extends Comparable> syntax mean?

In this week’s lab, many of the functions have syntax that looks something like:

public static <Item extends Comparable> Queue<Item> mergeSort(
        Queue<Item> items) {
    ...
}

Which is something we haven’t seen yet! This strange syntax comes from the fact that we want to be able to use our MergeSort and QuickSort classes to sort a Queue regardless of whether it contains items of type String or Integer or Glorp. In the example above, writing <Item extends Comparable> means that the mergeSort function operates on a Queue of generic type Item, which must extend Comparable (we need Item to extend Comparable so that we can use the compareTo method to compare items).

In other words, you can interpret the declaration above as saying “the mergeSort function takes a Queue of things that implement the Comparable interface, and returns a Queue of those things in sorted order.” If you’re unsure how to write code in functions like this, take a look at the helper functions that we provided, which may be helpful examples.

As well, here are the lecture slides from Spring 2017 covering this syntax in more depth.

My code works fine but the autograder fails with some sort of JSON error.

The issue is probably that your code is quadratic time instead of linearithmic. Your code should be able to easily handle collections of 10,000 items, even if there are lots of duplicates and/or the collection is in sorted order already.