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:
- Mergesort demo
- Mergesort slides
- Quicksort slides Slides 6 through 10. You'll be using the 3-way merge partitioning process described on slide 10. This approach, unfortunately, has no Hungarian dance video (but the partioning process they chose is pretty great to watch.)
(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.
queue package, you represent a SodaPrintr customer in a
User object. Every user has a user ID and a count of pages printed.
UserList class contains a
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
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.
- First, implement the helper function
partition(). This partitions a queue into three separating queues. Depending on sortFeature, these queues will contain Users with user ID or number of printed pages less than, equal to, or greater than the pivot item.
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.
- Next, implement
quickSort(), which sorts the
sortFeaturefrom least to greatest. Choose a random pivot.
Part 2: Implementing Mergesort
Implement mergesort in the UserList class. The implementation uses two helpers,
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).
- First, implement
makeQueueOfQueues(). This returns a
CatenableQueueobjects, each containing one user from the original
UserListclass. For example, if the original queue is [UserA, UserB, UserC], you want to return the queue [ [UserA], [UserB], [UserC] ]. Also,
userQueueshould be an empty queue when this method completes.
- Next, implement
mergeTwoQueues(). What this helper function does is take two sorted
CatenableQueuesand merge it to form one sorted
CatenableQueuethat contains all of the
Usersin both queues. (All sorting should be from least to greatest, by
sortFeature). This should run in Θ(N), where N is the total number of items in the combined queue.
- Lastly, implement
mergeSort(), which sorts the
sortFeaturefrom least to greatest. Writing this method requires some cleverness. It's a really neat puzzle. No helper methods are needed. Your method should be short (less than 12 lines of code).
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.
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.)