Homework 8: Sorting


Welcome to Sorting in HW8! This homework is intended to build familiarity with sorting algorithms by implementing quicksort and mergesort to sort linked lists. Since you all have had a busy few weeks with Midterm 2 and Proj2, this assignment is a "mini-homework" that should be shorter and more straightforwards than most homework assignments.

In class, we focused on sorting arrays. In this HW, we'll learn how to sort linked lists. The code should be relatively straightforward, but the ideas will require some cleverness and a good understanding of how mergesort and quicksort operate.

If you need to review, you might find the following helpful:

Startup Idea!

(A fun background context story you don't really have to read.)

As the end of the semester approaches, you realize that you can't possibly use up all of your free 61B printing! But one evening, you see your unhappy roommate returning from Main Stacks after spending $10 on printing. Ten dollars?! That's ridiculous! This gives you an idea for a new app. You gather some of your 61B friends and hack together SodaPrintr, a mobile app that allows non-CS/EECS students to use leftover printing pages from CS/EECS students.

After creating a few flyers and t-shirts, getting a TechCrunch spotlight article, and receiving venture capital funding, your app becomes an overwhelming success! "A new era has begun! This printing revolution will change college culture! BIG DATA!" shouted your happy customers. Soon enough, there are too many print requests for the CS students to handle. How will we handle who gets their request satisfied first?

Your team narrows it down to two options: You can first serve the customers who have used SodaPrintr the longest (to reward customer loyalty), or you can first serve the customers who have printed the fewest pages (to reward good environmentalism). Since the rest of your team is busy working on Proj3, it's up to you to implement sorting functionality!

Let's look at the code.

You are organizing your users using a queue data structure. This can be found in the queue package. The CatenableQueue class is a special queue in that you can append two queues in constant time. The QueueNode class contains an object and a next node.

Outside the queue package, you represent a SodaPrintr customer in a User object. Every user has a user ID and a count of pages printed.

Your UserList class contains a CatenableQueue of Users. You can add new users by passing in how many pages the new user printed as their first order. Their user ID will be the next consecutive ID. (For example, if you have 3 users, their user IDs will be 0, 1, 2. If you add a new user, this new user's ID will be 3.)

Become familiar with the class structure by reading the method descriptions. The classes have methods that will help you implement sorting. You will be adding to the UserList class by adding sorting functionality. Please keep your changes to the UserList class.

WARNING: You are provided with a very naive test in UserList. All this test does is check if you have the right idea for what to do. (It tests that you are sorting the right feature from least to greatest, rather than greatest to least or something like that.) Passing this test does NOT guarantee that your code works. You should be writing unit tests that further test the functionality of your code.

Note that the abstraction barriers in UserList are very artificial and are not reflective of how a real project should be organized. For example, it's a bad idea to have sorting routines hard-coded into a class like this, but we've chosen to do this for this HW to keep things simple.

Also, for this homework, the autograder tests will be the same as the secret tests. But the autograder error messages are rather vague, so it is still recommended you write your own tests.

Part 1: Implementing Quicksort

Implement quicksort in the UserList class. This method uses a helper, partition(). Since you haven't decided if you're going to sort by the User ID or by the number of pages printed, quickSort() takes in two parameters: the first is a string that tells which feature you need to sort by, and the second is the queue you need to sort.

NOTE: I've found this is a common misconception that I should have clarified: Pivot is the ID or printed pages number you compare to, NOT the index of the user you compare to. For example—If pivot is 5 and you're partitioning on IDs, you should separate the lists into Users with an ID of less than 5, Users with an ID of 5, Users with an ID greater than 5. You should NOT separate into Users with an ID greater than the 5th User's ID, etc.

Part 2: Implementing Mergesort

Implement mergesort in the UserList class. The implementation uses two helpers, makeQueueofQueues() and mergeTwoQueues(). Your mergesort implementation should NOT be in place, i.e. it's ok to use Θ(N) memory (in-place mergesorts are slower and much tricker to write).

Part 3: A Solution for Customer Loyalty

The SodaPrintr team comes up with a compromise. You will sort the customers based on the number of pages printed! (This also discourages users who print too many pages.) However, if two users have printed the same number of pages, the user with the older account should come first.

Example: UserA's user ID is 1 and has printed 4 pages. UserB's user ID is 2 and has printed 3 pages. UserC's user ID is 3 and has printed 4 pages. The correct sorting is UserB, UserA, UserC.

Implement sortByBothFeatures() in UserList, using your implementations of Mergesort and Quicksort. You don't have to use both Mergesort and Quicksort, but you can if you want to. (Hint: Don't overthink it. This method is very short—under 5 lines. It is almost entirely conceptual.)