Lab 4

due: Monday March 10 11:59pm (submit on Gradescope here).

Goals:

In this lab, you'll implement the Bucket Sort algorithm. The starter code for the BucketSorter class can be downloaded here. Similar to what we did in class on Wednesday March 5, you'll work on this lab in pairs using the Live Share extension in VS Code. Note that only the person starting the Live Share server will have a copy of the code. At the end of class, make sure that everyone has their own copy of the code so you can complete it after the lab.

As in class, choose one group member to start the Live Share server by clicking on Live Share. Then send this link to the other group member(s). Please work in pairs. If necessary, you can form a group of 3 but no higher than this please (this limit has been set in Gradescope).

Bucket Sort steps

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.

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:

ArrayList<ArrayList<Integer>> buckets = new ArrayList<>();

The steps below describe the Bucket Sort algorithm:

  1. Find the maximum value in the array of items (Part 1 below). Call this maxValue.
  2. Create an ArrayList of ArrayList<Integer> called buckets (see above).
  3. Add numBuckets empty ArrayList<Integer>s to buckets.
  4. For each item in items:
         a. Find the index of the bucket this item should be placed in (Part 2 below). Call this bucketIndex.
         b. Add item to the bucket at the index from Step 4a, i.e. buckets.get(bucketIndex).
  5. For each bucket in buckets:
         a. Sort the items in the bucket. Use Collections.sort.
  6. For each bucket in buckets:
        For each item in bucket:
             a. Place item into items.

Part 1: implement the getMaxValue method

First, complete the getMaxValue method. When you complete the sort method (Part 3), you should call getMaxValue to retrieve the maximum value.

Part 2: implement the whichBucket method

When you complete the sort method (Part 3), you should call whichBucket to determine which bucket to put an item in (Step 4a). This method takes in the item in question (item), the maximum value in the array (maxValue) and the number of buckets (numBuckets).

To determine the bucket index, we can first think about mapping all the array values to the $[0, 1]$ range. This can be done by dividing each item by the maximum value (which is why we needed maxValue). The resulting floating-point numbers (within $[0, 1]$) can then be multiplied by the number of buckets to get a number on the range from 0 to numBuckets. Since buckets are numbered from 0 to numBuckets - 1, the result should be rounded down using Math.floor. Ultimately, this might be implemented as:

return (int) Math.floor((double)item * numBuckets / (maxValue + 1));

Note the use of casting to make sure we end up with a floating-point number (double) before calling Math.floor and then finally a cast to an int during the return. An alternative is to use Math.floorDiv. Also note that we use maxValue + 1 in the denominator. Otherwise, we might end up with a bucket index that is out-of-bounds of buckets.

Part 3: implement the sort method

Follow the steps above to complete the Bucket Sort algorithm in the sort method. Test your code by adding a PSVM (maybe try the example in the notes from Lecture 4W). Gradescope will check that a PSVM has been added.

Part 4: implement the isSorted method

Finally, complete the isSorted method to determine if an array is sorted. Return true if it is sorted, and false otherwise.

Submission

Upload the BucketSorter.java file to Gradescope. Since you worked on the code as a group, you can submit as a group or you can submit individually if you prefer. See this video for instructions on how to submit as a group.

Remember to check the style of your code!