MP3: Practical Sorting

Created By: Geoffrey Challen
/ Updated: 2021-11-20

We begin MP3 by discussing how to approach sorting problems in real code, including using built-in sorting functionality and performing sorts that consider multiple properties. This will both connect with our previous discussions about sorting, provide some real-world practice, and continue our work with lambda methods.

Practical Sorting

Before we examine our first test case for MP3, let's discuss practical approaches to sorting in Java. While sorting algorithms are fun to implement and analyze, in practice you should never implement your own sorting algorithm! The sorting algortihms already provided by Java are far more sophisticated and efficient than anything you could implement on your own.

Instead, practical sorting frequently focuses on how to sort objects, particularly when they have multiple keys and we might want to sort them in different ways. Let's examine this together and see how to use Java's built-in sorting capabilities to accomplish this task.

Demonstrate how to use Collections.sort and how to do a multi-property sort.

Sorting Related Restaurants

To get started with MP3, follow the usual steps documented here. Once you've installed the test suites and reconfigured grade.yaml, pick up below.

Next let's review what you need to complete to pass today's test case. However, this one is largely algorithmic, so you'll want to refer to the complete description below.

Briefly discuss what getRelatedInOrder needs to do, and some of the challenges here.

As a more complete description of your task, you should complete a new method getRelatedInOrder on your existing RelatedRestaurants class as follows. getRelatedInOrder should take a String containing a restaurant ID and return a List<Restaurant>. The list of restaurants should contain all of the restaurants that are related to the one with the passed ID. The list should be sorted with the most-related restaurants first, and within each group with the same score restaurants should be sorted by name. If the restaurant ID passed to getRelatedInOrder is not valid, you should throw an IllegalArgumentException.

For example, again say that I like both Thara Thai and Chipotle, and Colleen likes Thara Thai, Chipotle, Big Grove, and Sakanaya. Then the sorted list of related restaurants returned by getRelatedInOrder if the ID passed corresponds to Thara Thai would be: Chipotle, Big Grove, Sakanaya. Chipotle is first because it appears with Thara Thai in both my list and Colleen's. Big Grove and Sakanaya are next, because they appear with Thara Thai in Colleen's list, and Big Grove is first because they are sorted by name.

A few notes:

  • You'll probably want to use your existing getRelated method.
  • Note that the returned List is a list of Restaurants, not Strings. So you may need a way to convert restaurant IDs to Restaurants, possibly using a map.
  • You may need to add code to your existing constructor to help solve this problem.
  • You'll want to review some of the methods that we discuss above for sorting Lists in Java

No Homework Today

As a reminder, on lessons where we focus on the machine project we will not assign a homework problem! However, the lesson will usually focus on helping you complete a particular part of the MP test suite, and so we encourage you to spend time on that in lieu of a homework problem.

Today your goal should be to complete the first MP3 test case: testGetRelatedInOrder.

If you get stuck, find us for help on the help site or forum.