This sorting technique takes on the similar thought brought forth by the Modified Quick Sort. It also wants to leverage on the efficiency of Insertion Sort when the array is small enough and potentially already partially sorted. It aims to realize this approach by dividing and gathering similar inputs into different, then applying insertion sort on each bucket that has at least one input element, and finally retrieving the sorted elements in order from each bucket. These are videos that show you how Bucket Sort functions: video1, video2. Examine the existing implementation. The comments marked as //TODO indicate areas where specific lines of code are needed to complete the sorting algorithm successfully. Two helper methods, assignNumBuckets and assignBucketIndex, have been implemented already for you. You do not need to modify these, but make sure you know how they work.
starter code
//Provided imports, feel free to use these if needed
import java.util.Collections;
import java.util.ArrayList;
/**
* TODO: add class header
*/
public class Sorts {
/**
* this helper finds the appropriate number of buckets you should allocate
* based on the range of the values in the input list
* @param list the input list to bucket sort
* @return number of buckets
*/
private static int assignNumBuckets(ArrayList<Integer> list) {
Integer max = Collections.max(list);
Integer min = Collections.min(list);
return (int) Math.sqrt(max - min) + 1;
}
/**
* this helper finds the appropriate bucket index that a data should be
* placed in
* @param data a particular data from the input list if you are using
* loop iteration
* @param numBuckets number of buckets
* @param listMin the smallest element of the input list
* @return the index of the bucket for which the particular data should
* be placed in
*/
private static int assignBucketIndex(Integer data, int numBuckets, Integer listMin) {
return (data - listMin) / numBuckets;
}
/**
* This method performs bucket sort on the input arraylist
*
* @param list The arraylist we want to sort
*/
public static ArrayList<Integer> bucketSort(ArrayList<Integer> list) {
ArrayList<ArrayList<Integer>> buckets = new ArrayList<>();
int numBuckets = assignNumBuckets(list);
for (int i = 0; i < numBuckets; i++) {
ArrayList<Integer> freshBucket = new ArrayList<>();
buckets.add(i, freshBucket);
}
Integer listMin = Collections.min(list);
for (Integer data : list) {
int bucketIndex = assignBucketIndex(data, numBuckets, listMin);
// TODO // Adds data to correct bucket
}
ArrayList<Integer> sortedList = new ArrayList<>();
for (ArrayList<Integer> bucket : buckets) {
if (bucket.size() > 0)
Collections.sort(bucket);
//TODO // Adds all elements in bucket to sortedList
}
return sortedList;
}
/**
* This method performs count sort on the input arraylist
*
* @param list The arraylist we want to sort
*/
public static ArrayList<Integer> countSort(ArrayList<Integer> list) {
ArrayList<Integer> output = new ArrayList<Integer>();
// Find the largest element of the array
int max = list.get(0);
for (int i = 1; i < list.size(); i++) {
if (list.get(i) > max)
max = list.get(i);
}
int[] count = new int[max + 1];
// Initialize count array with all zeros.
for (int i = 0; i < max; ++i) {
count[i] = 0;
}
// Initialize output with all zeros.
for (int i = 0; i < list.size(); ++i) {
output.add(0);
}
// Store the count of each element
for (int i = 0; i < list.size(); i++) {
int value = list.get(i);
// TODO // increment count array at correct index
}
// Store the cumulative count of each array
for (int i = 1; i <= max; i++) {
// TODO
}
// Find the index of each element of the original array in count array, and
// place the elements in output array
for (int i = 0; i < list.size(); i++) {
count[list.get(i)]--;
output.set(count[list.get(i)], list.get(i));
}
return output;
}
////////////////////////
///// EXTRA CREDIT /////
////////////////////////
public static boolean inspectInsertion(int[] arr, int n) {
// TODO
return false;
}
public static boolean inspectSelection(int[] arr, int n) {
// TODO
return false;
}
public static boolean inspectMerge(int[] arr, int n) {
// TODO
return false;
}
}
Step by step
Solved in 2 steps
