Project 3: Grit Sort and Scapegoat Trees
Due: Friday, March/11/2022 at 11:59 PM
General Guidelines:
The APIs given below describe the required methods in each class that will be tested. You may need addi�onal methods
or classes that will not be directly tested but may be necessary to complete the assignment. Keep in mind that anything
that does not need to be public should generally be kept private (instance variables, helper methods, etc.).
Unless otherwise stated in this handout, you are welcome (and encouraged) to add to/alter the provided java files as well
as create new java files as needed.
In general, you are not allowed to import any additional classes or li
aries in your code without explicit permission from the
instructor! Adding any additional imports will result in a 0.
Note on Academic Dishonesty:
Please note that it is considered academic dishonesty to read anyone else’s solu�on code to this problem, whether it is
another student’s code, code from a textbook, or something you found online. You MUST do your own work!
HARDCODING IS ACADEMIC DISHONESTY. You will not pass any Vocareum test cases if you hardcode and will end up
ge�ng 0 for the project.
Note on using the starter code:
You are not required to use the starter code. However, keep in mind that (1) some API methods are already implemented
for you, and (2) if you do not use the starter code, you s�ll need all the defined methods below without changing any
eturn types or names. Your code must work with the tests that are provided.
Note on implementa�on details:
Note that even if your solu�on passes all test cases, if a visual inspec�on of your code shows that you did not follow the
guidelines in the project, you will receive a 0.
Note on grading and provided tests:
The provided tests are to help you as you implement the project. The Vocareum tests will be similar but not exactly the
same. Keep in mind that the points you see when you run the local tests are only an indicator of how you are doing. The
final grade will be determined by your results on Vocareum.
From the syllabus: “If your code passes the given test cases in your machine but fails in Vocareum means you do not
consider in your solu�on other cases that may occur. It is your responsibility to figure out such cases and develop a more
obust solu�on.”
It may occur your code works fine locally but does not in Vocareum. In such a case, check that every member variable and
func�on has their respec�ve access modifier (public, private, or protected). Also, check you import default Java API
packages and submi�ed the required .java files. Look at the e
or report thrown by Vocareum for addi�onal informa�on.
Do not expect the report to be concise. You need to put your debugging skills to work.
IMPORTANT: Passing the given local test cases does not guarantee your solu�on works for every possible input value o
scenario. We will not do manual grading of your code. We grade objec�ve results, not effort.
Project Overview:
In this project, you will work on two problems. First, a hy
id sor�ng method based on Inser�on Sort and Merge Sort,
called Grit Sort. And second, a self-balancing Binary Search Tree called Scapegoat Tree, for sor�ng tuples.
Part 1: Grit Sort (45 Points):
In real life, some sor�ng implementa�ons are a mixture of classical sor�ng methods and assump�ons over the data. Fo
example, the default sor�ng method in Java is Timsort (h�ps:
en.wikipedia.org/wiki/Timsort), which assumes data is
almost sorted. You will work on a similar sor�ng method called Grit Sort. We will assume data has chunks of sorted data.
Let us consider a list of Integers A = {3, 5, 6, 8, 10, 2, 4, 5, 6, 1, 2, 4, 5}.
Let us call a sorted sub-list in list A a chunk. List A has 3 such sorted chunks.
Chunk x = {3, 5, 6, 8, 10}
Chunk y = {2, 4, 5, 6}
Chunk z = {1, 2, 4, 5}
https:
en.wikipedia.org/wiki/Timsort)
The mo�va�on for Grit Sort is to take advantage of these pre-sorted chunks. Grit sort is a sor�ng method that you will be
wri�ng which leverages both bucket sort and merge sort to speed up the sor�ng in par�ally sorted lists.
The steps for Grit Sort are the following:
Slice the generic a
ay A by sorted chunks. Each chunk goes into a bucket, depending on the chunk's size. This step
is an O(n) opera�on, where n is the length of the input a
ay A.
Merge the chunks in each bucket. The run�me here is hard to tell since sorted chunks vary in size. We can loosely
say it takes O(n/m) on average.
Merge all buckets in A.
The algorithm finishes a�er merging all the buckets.
Important points/cases to consider:
A bucket can have 0 or more chunks. In the example above, the bucket which keeps track of chunks of size four will
have two chunks, while the bucket for size five will only have 1. Naturally, a bucket can have more than two chunks.
Remember that each chunk is sorted. Assuming a bucket has k sorted chunks in it, we need to merge these k sorted
lists.
A chunk can be of size 1.
Starter Code:
You have been provided with helper func�ons in Sor�ng.java which will help you to implement the required func�ons.
You are free to make any more helper func�ons that you may require. All the func�ons in Sor�ng.java can be called in
GritSort.java by making a Sor�ng object.
Func�on Descrip�on
greaterThan(A
ayList
- list, int i, int j) returns true
if the Item at index @param ‘i’ in @param list is greate
than Item at index @param ‘j’
else
eturns false
lessThan(A
ayList- list, int i, int j) returns true
if the Item at index @param ‘i’ in @param list is lesser than
Item at index @param ‘j’
else
eturns false
equal(A
ayList- list, int i, int j) returns true
if the Item at index @param ‘i’ in @param list is equal to the
Item at index @param ‘j’
else
eturns false
greaterThan(Item i, Item j) returns true
if the Item @param ‘i’ is greater than Item @param ‘j’ else
eturn false
lessThan(Item i, Item j) returns true
if the Item @param ‘i’ is less than Item @param ‘j’ else
eturn false
equal(Item i, Item j) returns true
if the Item @param ‘i’ is equal to the Item @param ‘j’ else
eturn false
swap(A
ayList- list, int i, int j) Swaps the element at index @param ‘i’ with element at
index @param ‘j’ in the @param list.
print(A
ayList- list) prints the Items in the @param list.
Methods to Implement:
These are the func�ons that you must implement for part 1.
In Sor�ng.java (20 points)
public A
ayList- mergeSort (A
ayList- list)
This func�on takes in an A
ayList and returns the sorted list using merge sort as the sor�ng method. You are
equired to implement merge sort as taught in class.
public A
ayList- insertionSort (A
ayList- list)
This func�on takes in an A
ayList and returns the sorted list using inser�on sort as the sor�ng method. You are
equired to implement inser�on sort as taught in class.
In GritSort.java (25 points)
public A
ayList- grit (A
ayList- list)
This func�on takes in an A
ayList and returns the sorted list using grit sort as the sor�ng method. You are required
to implement grit sort as described previously.
public A
ayListayList makeChunks (A
ayList- list)
This func�on takes in a list and returns an A
ayList of A
ayList. Each chunk found is stored in an a
ay list and then
all the chunks (which are A
ayList- ) are then in- turn stored in an a
ay list which is then returned.
public HashMapayListayListmakeBuckets(A
ayListayList chunks)
This func�on takes in an A
ayList of A
ayList and returns an HashMapayListayList.
Chunks of the same size are stored in the same bucket (Each chunk of the size say S is stored in a bucket which
co
esponds to that size S). Thus, for the returned HashMap, the key is the chunk size, and the co
esponding value
is a list of chunks of that size.
public A
ayList- mergeChunk (A
ayListayList bucket)
This func�on takes in a bucket (A
ayList of A
ayList) and returns an A
ayList which has the chunks in the bucket
merged. For example, let’s say that a bucket has 5 chunks (A
ayList- ) in it, the func�on will merge these lists
and return the merged and sorted list with the elements from all the 5 chunks.
Code modularity: You must implement makeChunks(), makeBuckets(), and mergeChunk() and use them in grit(). This is
also specified in the TODO part in the starter code.
Other Informa�on:
We use a generic class for this part of the project. For more informa�on about generic classes please refe
h�ps:
docs.oracle.com/javase/tutorial/java/generics/types.html
The name ‘Item’ is a type parameter, a symbolic placeholder for some concrete type to be used by the client. (Ex.
String, Integer, etc.)
Our type parameter extends ‘Comparable’. This is so that the type parameter (- ) supports comparison with
other instances of its own type.
The class will be instan�ated as follows (for Integer): Sor�ng s = new Sor�ng
();
You can similarly make it for other data types such as Strings, A
ays and even Objects of other classes. Therefore,
implemen�ng this generic class will enable you to sort Integers, Strings, and other data types as well.
to implement the required func�ons. You are free to make any more helper func�ons that you may require. All the
func�ons in Sor�ng.java can be called in GritSort.java by making a Sor�ng object.
Tes�ng:
You are provided with three test files and sample test classes under the startercode/test folder. You can download them
and test them locally.
To test your code in Sorting.java , run the SampleSortingTest.java . This will read the data in the specified test files,
call inser�onSort() and mergeSort() func�ons in your Sor�ng.java to sort the data and check if they sort the data
co
ectly. Co
ectly sor�ng the data in a test file will get 4 points (2 for inser�onSort and 2 for mergeSort), so you
will get 12 points if your code passes all three test cases. When you submit the code on Vocareum, we will use five
test cases to test your code, the maximum points for this part is 20.
To test your code in GritSort.java , run the SampleGritSortTest.java file. For each test case, let's say test1.txt fo
example, this reads the data in the test1.txt, calls the makeChunks() in your GritSort.java, and compares the returned
esult with the standard result in test1_chunks.txt (1 point for each test file). Then, it calls makeBuckets() in you
GritSort.java and compares the returned result