Hi,I finished the sorting.java, and now I am on the gritsort.java, however, the code doesn't work yet, and I haven't coded the rest for part 2.
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 libraries 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 return 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 robust 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 error 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 or 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 hybrid 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. For 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 array 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 array 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(ArrayList
- list, int i, int j) returns true if the Item at index @param ‘i’ in @param list is greater than Item at index @param ‘j’ else returns false lessThan(ArrayList
- 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 returns false equal(ArrayList
- 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 returns false greaterThan(Item i, Item j) returns true if the Item @param ‘i’ is greater than Item @param ‘j’ else return false lessThan(Item i, Item j) returns true if the Item @param ‘i’ is less than Item @param ‘j’ else return false equal(Item i, Item j) returns true if the Item @param ‘i’ is equal to the Item @param ‘j’ else return false swap(ArrayList
- list, int i, int j) Swaps the element at index @param ‘i’ with element at index @param ‘j’ in the @param list. print(ArrayList
- 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 ArrayList
- mergeSort (ArrayList
- list) This func�on takes in an ArrayList and returns the sorted list using merge sort as the sor�ng method. You are required to implement merge sort as taught in class. public ArrayList
- insertionSort (ArrayList
- list) This func�on takes in an ArrayList and returns the sorted list using inser�on sort as the sor�ng method. You are required to implement inser�on sort as taught in class. In GritSort.java (25 points) public ArrayList
- grit (ArrayList
- list) This func�on takes in an ArrayList and returns the sorted list using grit sort as the sor�ng method. You are required to implement grit sort as described previously. public ArrayList<>
- > makeChunks (ArrayList
- list) This func�on takes in a list and returns an ArrayList of ArrayList. Each chunk found is stored in an array list and then all the chunks (which are ArrayList
- ) are then in- turn stored in an array list which is then returned. public HashMap<>
- >> makeBuckets(ArrayList<>
- > chunks) This func�on takes in an ArrayList of ArrayList and returns an HashMap<>
- >>. Chunks of the same size are stored in the same bucket (Each chunk of the size say S is stored in a bucket which corresponds to that size S). Thus, for the returned HashMap, the key is the chunk size, and the corresponding value is a list of chunks of that size. public ArrayList
- mergeChunk (ArrayList<>
- > bucket) This func�on takes in a bucket (ArrayList of ArrayList) and returns an ArrayList which has the chunks in the bucket merged. For example, let’s say that a bucket has 5 chunks (ArrayList
- ) 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 refer 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, Arrays 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 correctly. Correctly 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 for example, this reads the data in the test1.txt, calls the makeChunks() in your GritSort.java, and compares the returned result with the standard result in test1_chunks.txt (1 point for each test file). Then, it calls makeBuckets() in your GritSort.java and compares the returned result