Looking for Help with Assignments?

-RUCats has 80 hours of tutoring available online and in-person. Check the tutoring tab in Canvas!
-Instructors and Lead TAs have a combined 10 hours of Office Hours, open to all sections. See times/locations here.
-Piazza (found in the Canvas sidebar) provides fast support from Course Staff and other Students. Be sure to search to see if someone has asked a similar question!
-If you need a computer to complete work on, iLab machines can be found in the CSL (Hill 252) and surrounding rooms.

Mario Sort - 10 Course Points

The purpose of this assignment is to learn how to implement and use two of the elementary sorts (Merge Sort and Insertion Sort)

You can download and submit the project files via Autolab.

Sorting Algorithms

Sorting is one of the most basic and fundamental concepts in computer science and has the broadest applications. There are many examples of problems which can be solved by sorting.

A customer searching through products (by price, by popularity, by rating…)
An airport sorting luggage from multiple flights
A bank detecting anomalies in large amounts of transactions

Two of the elementary sorts we learn are Selection Sort and Insertion Sort. Two of the non-elementary sort we learn are Merge Sort, and Quick Sort. For this lab, you will only be responsible for coding Insertion Sort and a piece of Merge Sort. If you are unfamiliar with the steps required for the above two sorts, please review the following lecture slides:

Overview

Welcome to the mushroom kingdom! Here, Racers and Players test their driving and board game skills in races and minigames against the Mushroom Kingdom’s best! After these events take place, we need to manually sort the contestants which takes us days. Now we need you to come up with a way to find a winner more efficiently!

Provided Classes

Mario Sort uses a few supporting classes for input/out as well as storing data about contestants. In the project folder, you are provided the java files for these classes, MarioSort.java, Player.java, Racer.java, StdIn.java, StdOut.java, Driver.java. StdIn.java: This class includes methods for reading from the terminal/a file StdOut.java: This class includes methods for printing to the terminal/a file Player.java: This class stores data about a single Mario Party player, including their name, num stars, and num coins. Winners are determined by who has the most stars. If a tie exists, then coins are used to break it. Racer.java: This class stores data about a single Mario Kart racer, including their name, and an int[] array of lap times. A getAverage() method exists to get the average lap time, which is used to determine a winner. Driver.java: This is a simple visualization class which can load any of the input files, and then sort them. You can use this to test your code, and determine if you are sorting properly. MarioSort.java: This is the only file you will code in, and is the file you will submit to Autolab. Fill in the marioKartSort() method, the marioPartySort() method, and mergeHelper() method according to the descriptions below.

Directions

DO NOT add new import statements.
DO NOT add any new class attributes
DO NOT change any of the method’s signatures.
DO NOT modify the given constructor.

To complete this Lab, you will fill in MarioSort.java with the solutions for marioKartSort(), marioPartySort(), and mergeHelper(). The merge() method for merge sort is given to you. The readData() method to read input files is also provided (along with getter methods).

To Run: run the following commands from the innermost MarioSort directory, containing the src and bin folders.

Compile:
1. javac -d bin -cp lib/cs112.jar src/mario/*.java
Run:
1. Windows: java -cp “lib/cs112.jar;bin” mario.Driver
2. Mac/Linux: java -cp bin:lib/cs112.jar mario.Driver

OR: Run through VSCode, ensuring you open the correct innermost MarioSort directory

readData() [PROVIDED]

THIS METHOD IS PROVIDED TO YOU. This reads in racer/player data from a CSV, and populates the corresponding array.

Filenames containing “kart” (for Mario Kart) will be expected to contain Racer object info, and will populate the marioKart array.
Filenames containing “party” (for Mario Party) will be expected to contain Player object info, and will populate the marioParty array.

Do NOT change the input file names. If you create custom input files, make sure they follow the above naming scheme.

marioKartSort()

This method needs to implement insertion sort in order to sort winners of a Mario Kart race. Winners are determined by their average lap time (using the Racer getAverage() method). The marioKart array already contains the Racer objects which you should sort. After this method is called, the marioKart array should be sorted in ascending order by average lap time. If the marioKart array is null or length is 0, then simply return. View the lecture slides for Insertion Sort implementation details for Java. Note that the format of this lab may be slightly different, but the algorithm is identical. You are allowed to create any helper methods if needed, but they are not required. How to test: run the driver (see the How to open + run section below), then select “marioKart1.csv” or “marioKart2.csv” under the dropdown menu. Then click the load button to see the unsorted data and click the Sort button to see it sorted. The racers will be sorted by their average lap time, with the fastest racers at the top. Update 9/24: If you downloaded the handout before 9/24 at 4pm, then re-download it and replace your Racer.java file with the new one.

marioPartySort() [PROVIDED]

THIS METHOD IS PROVIDED TO YOU. This simply calls the mergeHelper() method (next task), to start your recursive merge sort algorithm.

mergeHelper()

This method is what drives merge sort, and recursively breaks down the array by half. ONLY IF the left param is < the right param:

calculate the middle index as left + (right-left)/2
call mergeHelper() with the params arr, left, middle
call mergeHelper() with the params arr, middle+1, right
call merge() with the params arr, left, middle, right

How to test: run the driver (see the How to open + run section below), then select “marioParty1.csv” or “marioParty2.csv” under the dropdown menu. Then click the load button to see the unsorted data and click the Sort button to see it sorted. This tests merge sort as a whole. Players will be sorted first by the number of stars they have, and any tiebreakers are settled by the number of coins. The player with the most stars will be at the top once the array is sorted, and so on.

merge() [PROVIDED]

THIS METHOD IS PROVIDED TO YOU. This method handles merging two subarrays of a larger array, such that both subarrays end up merged and sorted together. This is what actually “sorts” the elements for merge sort. You will call this method in mergeHelper().

How to open + run

First things first, make sure you have VS Code installed, a Java Development Kit (JDK) installed, and the Java Extension Pack enabled on VS Code. If you don’t, the FAQ tab of this site has download links.

Afterward, open the CatIsland folder in VS Code using File -> Open Folder. Open the MarioSort folder that directly contains the bin, src, and lib folders. If you have a MarioSort folder inside MarioSort, or you have CS112 Code -> MarioSort, you must open the innermost MarioSort folder.

Next, when you’re ready to run your program, you can use either the terminal or the VS Code run option.

If you use the terminal, run the following commands in order from the MarioSort directory that contains the bin, src and lib folders. If you’re having issues, please ensure that you’re in the right directory in VS Code and that you’ve typed the commands correctly and in order.

Compile:
1. javac -d bin -cp lib/cs112.jar src/mario/*.java
Run:
1. Windows: java -cp “lib/cs112.jar;bin” mario.Driver
2. Mac/Linux: java -cp bin:lib/cs112.jar mario.Driver

You can also use the “Run” option in VS Code to run your program by right-clicking Driver.java and selecting “Run Java”.

Before submission

REMOVE all print statements you have written in MarioSort.java..

Collaboration policy. Read our collaboration policy on the course syllabus.

Submitting the assignment. Submit MarioSort.java separately via the web submission system called Autolab.

Getting help

If anything is unclear, don’t hesitate to drop by office hours or post a question on Piazza.

Find instructors and Lead TAs office hours here
Find tutors office hours on Canvas -> Tutoring
In addition to office hours we have the Coding and Social Lounge (CSL), a community space staffed with lab assistants which are undergraduate students further along the CS major to answer questions.

By George Janulis and Maaz Mansuri

Rutgers is an equal access/equal opportunity institution. Individuals with disabilities are encouraged to direct suggestions, comments, or complaints concerning any
accessibility issues with Rutgers websites to accessibility@rutgers.edu or complete the Report Accessibility Barrier / Provide Feedback form.