CS113 Lab 9: Sorting

Due Thursday, November 17 Wednesday November 23rd, before midnight


  • Read data from a file

  • Use lists and classes to store data

  • Use search and sort to work with a real-life data set

You are given basecode and data for this assignment. Check your dropbox to get started!

Restaurant dataset

For this assignment, we will be working with data from a real life dataset maintained by Yelp. Yelp provides information and reviews for a wide range of businesses. We will look at a subset containing only restaurants, bars, and cafes.

The dataset is available as a CSV file (CSV stands for "comma separated values"). Each line of the file contains information for a single restaurant. The restaurants are listed in the file in alphabetical order by name.

How have two datasets to work with in this assignment. They can be found in your dropbox.

  • restaurants.csv

  • restaurants-small.csv

Below is an example line.

1 Pot,Calgary,AB,31,3.500000,Buffets; Chinese; Hot Pot; Restaurants; Dim Sum; Asian Fusion; Fondue

Each line contains the following information.

  • Restaurant name ("1 Pot")

  • City where restaurant is located (Calgary)

  • State/Provence where restaurant is located (AB)

  • Number of reviews (31)

  • Average review (3.5)

  • Categories for the restaurant (Buffets; Chinese; Hot Pot; Restaurants; Dim Sum; Asian Fusion; Fondue ) Categories are separated with a ;

1. Restaurant class

Implement a class, Restaurant, in the file Restaurant.java. This class should hold the data we read in from our CSV files. This class should also have accessors for each instance variable. Test your class in a main function defined in Restaurant.java.


  • Restaurant Name (String)

  • City (String)

  • State (String)

  • Average stars (double)

  • Number of reviews (int)

  • categories (array of String)


  • Constructor. This function should initialize the data inside Restaurant

  • Accessors for the restaurant name, city, state, review count, average review, and categories

    • public String getName()

    • public String getCity()

    • public String getState()

    • public int getReviewCount()

    • public double getStars()

    • public String[] getCategories()

Below is example output for a main which tests Restaurant.

$ java Restaurant
           Name: Test
           City: Philadelphia,PA
        Reviews: 10
          Stars: 3.5
     Categories: [BBQ, Cafe]

2. Restaurant utilities

Implement a class, RestaurantUtil, that implements two static functions for working with Restaurants.

2.1. Load

In the file, RestaurantUtil.java, write a function, Load, that reads a file containing restaurant information into an array.

This function should adhere to the following specification.

// Function: Load
// Read the restaurant information in filename and return an array of restaurants
// Input: filename (String), the file to read. Should be a CSV of restaurants
// Returns Restaurant[] (array of Restaurant)
public static void Restaurant[] Load(String filename)

Hints and recommendations:

  • Use the class In, defined in java-introcs, to load the file, e.g. In file = new In(filename)

  • Read in all the lines of the file at once using the function String[] lines = file.readAllLines()

  • Use the function, split, to split a string based on a character. For example String[] items = current.split(",") would split a line into an array of String based on commas.

  • Initialize an array of restaurants based on the number of lines

  • For each line, create a Restaurant object and save it in the array

2.2. Print

In the file, RestaurantUtil.java, write a function, Print, that prints the restaurants in an array. You may format the display how you wish, but the output should be clean and easy to read.

This function should adhere to the following specification.

// Function: Print
// Print the first `maxToShow` restaurants in the array restaurants
// Input: restaurants (Restaurant[]), an array containing restaurants
// Input: maxToShow (int), the number of items to show
// Returns none
public static void Print(Restaurant[] restaurants, int maxToShow)

2.3. Test

In the file RestaurantUtil.java, test Load and Print in main.

  • Load the file restaurants-small.csv

  • Call Print with maxToShow = 3

  • Call Print with maxToShow = 100

Below is sample output

$ java-introcs RestaurantUtil

                              Restaurant                    Location    Reviews Stars
                              ----------                    --------    ------- -----
                                   1 Pot                 Calgary, AB       31   3.5
                                    BRGR              Pittsburgh, PA      442   3.5
                             Brown Derby               Cleveland, OH       52   3.0

Showing 3 out of 12 restaurants

                              Restaurant                    Location    Reviews Stars
                              ----------                    --------    ------- -----
                                   1 Pot                 Calgary, AB       31   3.5
                                    BRGR              Pittsburgh, PA      442   3.5
                             Brown Derby               Cleveland, OH       52   3.0
                                 Eureka!               Las Vegas, NV      231   4.5
                                 Faberge                Montreal, QC      347   4.0
                                  Le Lab                Montreal, QC      230   4.5
                                Poke Bar               Charlotte, NC       26   4.0
                                     POP                 Toronto, ON        4   4.5
                           The Dog House               Cleveland, OH       10   4.0
                                The Haam                 Toronto, ON       83   4.0
                            Vitality Tap                 Calgary, AB        7   4.5
                             Wacky Wings             Mississauga, ON       96   3.0

Showing 12 out of 12 restaurants

3. Restaurant App

In the file, RestaurantApp.java, implement an application that lets users search for restaurant information from our dataset. Your application should have three features:

  • Searching for a restaurant by name

  • Summarizing the restaurants in a given city

  • Searching for restaurants that fit a given category

Below is sample output:

General hint and requirements:

  • Your program should not crash on bad input

  • Your program should have an option to Quit

  • We recommend you implement each feature in its own function.

  • We recommend you load the data set and implement your main application loop in main.

Below is a possible algorithm for your application’s main

dataset = Load("restaurant.csv")
while !timeToQuit
    show the options to the user
    ask the user for their choice
    if choice == 1
    else if choice == 2
    else if choice == 3

3.1. Search names

Implement a feature which allows the user to search by name.


  • Ask the user for the name to search for

  • The search should be case insensitive. Hint: Use toLowerCase() when comparing strings.

  • Because the names are alphabetized, use binary search to find a name

  • If a restaurant is found, display all its information in a table. Your output does not need to be identical, but it should be clean and easy to read.

  • You are not allowed to use any of Java’s built-in search functions.

3.2. City summary

Implement a feature which summarizes the restaurants for a given city.


  • Ask the user for a city and state to search

  • Prints the number of restaurants in that city

  • Prints the average number of reviews for a restaurant

  • Prints the max number of reviews for a restaurant

  • Prints the min number of reviews for a restaurant

  • Prints the average number of Stars

  • Outputs the results in a table with aligned columns

  • You may not use built-in min, max, or sum functions!

This dataset includes restaurants for Las Vegas, Phoenix, Mississauga, Toronto, Montreal, Calgary, Cleveland, Charlotte, Pittsburgh, Scottsdale.

3.3. Search categories

Implement a feature that allows the user to search restaurant categories for a keyword.


  • You are given a function searchCategoryByKeyword that returns an array of restaurants which match the keyword. Study this function to see examples of

    • Doing case-insenstive string comparisons (Hint: use toLowerCase())

    • The keyword can appear anywhere in the list of categories (Hint: use contains)

  • Sort the filtered restaurants by number of reviews

  • The program should show the name, location, review count, and stars for each restaurant

  • You may not use Java’s built-in sorting algorithms!

  • …​but you can implement any sorting algorithm you like best!

To implement this feature, you should first get a list of all restaurants that match the keyword. Then you should sort this list based on the number of reviews. Then, you should show the top 25 results to the user. Below is psuedocode for this feature

ask user for the keyword
Restaurant[] filtered = searchCategoryByKeyword(keyword, dataset)
if filtered has more than 0 items in it
   sort filtered by number of reviews (from most reviews to least)
   Print the top 25 items in filterByKeyword
   tell user that keyword is not found

4. What to hand-in

  1. The programs, Restaurant.java, RestaurantUtil.java, and RestaurantApp.java

  2. Make sure your programs have a header containing your name, date, and description.

  3. Make sure your program can run from the Dropbox directory. You should include the data files and any supporting files your program needs to run.

  4. Make sure your submitted program loads the large file, restaurants.csv

  5. A brief write-up containing your name, assignment number, and a few sentences about how long you spent on the assignment and any interesting customizations you made.

4.1. How to hand-in

  1. Copy your files to your dropbox, into the folder called A09.