Lab 4

Lab 4

GradescopeStarter Code
Due: Tuesday October 07, 2025 5:00PM
Goals:
  • Implement Bucket Sort.
  • Practice using ArrayList (for the buckets).
Submit these files:BucketSorter.java

In this lab, you'll implement the Bucket Sort algorithm.

Please start by sharing with your lab partner through VS Code live share!

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:
    1. Find the index of the bucket this item should be placed in (Part 2 below). Call this bucketIndex.
    2. Add item to the bucket at the index from Step 4a, i.e. buckets.get(bucketIndex).
  5. For each bucket in buckets:
    1. 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 from Lecture 4R). 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.