Implement a sorting utility function that you might use to test multiple sorting algorithms.
Implement Bucket Sort.
Implement Radix Sort.
Submit these files:SortingUtil.java,BucketSorter.java,RadixSorter.java
In this homework, you will implement the Bucket Sort and the Radix Sort algorithms for an array of integers, so please review the notes from Lecture 5T. When implementing Radix Sort, you will use a radix (base) of 10.
Part 1: Sorting Util
As a warm-up, you’ll implement a method isSorted method to determine if an array of integers is sorted in SortingUtil.java. Return true if it is sorted, and false otherwise.
Part 2: Bucket Sort
We’ll restrict our implementation to sorting a fixed-size array of non-negative int values called items. The sort method will also take in the number of buckets (numBuckets) to use. Note that all the BucketSorter methods are static.
Part 2.1: Implement the getMaxValue method
First, complete the getMaxValue method as described in the javadoc comments. When you complete the sort method (Part 2.2), you should call getMaxValue to retrieve the maximum value.
Part 2.2: Implement the sort method
We need to make a decision about how to represent and store the buckets. Here, we’ll use an ArrayList-of-ArrayList. Since we are working with int values, we’ll use:
The steps below describe the Bucket Sort algorithm:
Find the maximum value in the array of items (Part 2.1). Call this maxValue.
Create an ArrayList of ArrayList<Integer> called buckets (see above).
Add numBuckets empty ArrayList<Integer>s to buckets.
For each item in items:
Find the index of the bucket this item should be placed in (use the provided whichBucket method). Call this bucketIndex.
Add item to the bucket at the index from Step 4a, i.e. buckets.get(bucketIndex).
For each bucket in buckets:
Sort the items in the bucket. Use Collections.sort.
For each bucket in buckets:
For each item in bucket:
a. Place item into items.
Follow the steps above to complete the Bucket Sort algorithm in the sort method.
Part 3: Radix Sort
Next, you’ll implement the Radix Sort algorithm. Like we did with bucket sort, we will restrict our input to non-negative integers.
Part 3.1: Complete the getMaxDigits method
Radix Sort is implemented using a certain number of “passes”, which we denoted as \(k\) in class. The number of passes corresponds to the maximum number of digits we are using to represent numbers. In our base-10 Radix Sort example in class, the maximum number in the input array was 802, so the maximum number of digits was 3.
For a base of 10, the number of digits in an integer \(v\) (assume \(v \gt 0\)) is:
\[
k = \lfloor \log_{10}(v)\rfloor + 1.
\]
The notation \(\lfloor x \rfloor\) means the “floor” (using Math.floor) of some real number \(x\), which returns the largest integer less than or equal to \(x\). For example, \(\lfloor 2.2\rfloor\) is 2 and \(\lfloor 3\rfloor\) is 3. Note that Math has a built-in method for Math.log10.
Complete the getMaxDigits method to determine the maximum number of digits for some input integer.
Part 3.2: Complete the getDigit method
Recall that during each pass of Radix Sort with base 10, we need to create 10 buckets to hold our current items where each bucket corresponds to a particular digit from 0 to 9.
Therefore, we need a method to extract the \(d^{\mathrm{th}}\) digit of an integer in our array. As in class, we will start with the least significant digit (the rightmost digit) and proceed from right-to-left. The getDigit method will take in some integer called number and the digit we want to extract (starting from the rightmost digit) d.
Think about how you would extract the digits from the number 12345:
5 is (12345 / 1) % 10
4 is (12345 / 10) % 10
3 is (12345 / 100) % 10
2 is (12345 / 1000) % 10
1 is (12345 / 10000) % 10
Convert these steps into an algorithm and implement it in the getDigit method.
Part 3.3: Complete the sort method using Radix Sort
Assume each value is \(\ge 0\). Please review the steps we used to sort an integer array in the annotated slides from Lecture 5T (page 32) as well as the sorting examples (Radix Sort starts on page 123). During each pass, create a new set of 10 buckets to store the items for each digit (0 to 9) on this pass. Then go through every item and put them in the appropriate bucket. We recommend starting by using an ArrayList-of-ArrayList as we did in above, but note that Part 3.4 consists of doing this without ArrayLists at all. After each pass, put the items from the buckets back in the items array so you can treat them on the next pass.
Part 3.4: Refactor your sort method to avoid using ArrayLists
This part is only worth a small amount (manually graded) but it’s a good challenge! Remove the import java.util.ArrayList at the top of your RadixSorter.java file and rewrite your Radix Sort algorithm without using ArrayLists. Instead, use a jagged multi-dimensional array (page 16, lines 11 - 18) for the buckets. During each pass, you’ll need to do two loops through the items: (1) to determine how many items are in each bucket and (2) to place the items in each bucket. In between Steps (1) and (2) you’ll need to actually allocate the 10 buckets to have enough space to store them. Hint: for Step (1), you might want to use an additional array to store the number of items in each bucket so you know how much to allocate before Step (2).
Test Case Requirements
We’re keeping it simple for test case requirements this week. The only requirement is that you test BucketSort.sort and RadixSorter.sort on at least two different arrays each in their respective main methods! You might consider using the arrays we used in the sorting examples.
Documentation, Style, and Design
Documentation and Style
Checkstyle will run automatically when you submit to gradescope; up to 10% will be deducted by the autograder from the programming portion of your grade if you have > 2 types of checkstyle problems. Remember you can see more details on checkstyle on this page, including how to run it in vscode.
Design
I will do a manual review for design. Up to 5% may be deducted from your final score due to design problems. This will also include checking the quality (rather than just the form) of your javadoc comments!