The idea behind counting sort is to keep track of the counts of each element in the array, then use those counts to recreate the array in sorted order. For example, if you know the input array has 2 tens in it and 3 elements less than 10, then you can conclude that the sorted array will look like this: [x, x, x, 10, 10, ...]. In other words you know that a 10 must go at index 4, and a 10 must go at index 3. Counting sort is one sort that uses this concept to sort all elements in an array. These are videos that show you how Counting Sort works: 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. The steps to counting sort are: - Find the max element in the input array. - - - Create a counting array with size equal to the max element + 1. Now each index of the array serves as a separate counter. Iterate through the input array, and for each element, increment the corresponding index in the counting array by 1. For example, if the input array is [2, 3, 1, 3, 2] the counting array will be updated as follows: First element [2, 3, 1, 3, 2]: Increment the value at index 2, resulting in [0, 0, 1, 0] Second element [2, 3, 1, 3, 2]: Increment the value at index 3, resulting in [0, 0, 1, 1] Third element [2, 3, 1, 3, 2]: Increment the value at index 1, resulting in [0, 1, 1, 1] Fourth element [2, 3, 1, 3, 2]: Increment the value at index 3, resulting in [0, 1, 1, 2] Fifth element [2, 3, 1, 3, 2]: Increment the value at index 2, resulting in [0, 1, 2, 2] Modify the counting array to be a "running total". Meaning the value at an index k will be the count of elements in the input array that were less than or equal to k. Using the example array from above: [2, 3, 1, 3, 2], you would get a counting array: [0, 1, 3, 5] Input: [0, 1, 2, 2] Output: 0, 0+1; 0+1+2; 0+1+2+2 producing [0, 1, 3, 5] Create an output array the same size as the input array. Iterate through the input array again, for each element reduce its count in the counting array by 1, then place the element at that index in the output array, for example with an input array of [2, 3, 1, 3, 2] the iterations would be as follows: First element [2, 3, 1, 3, 2]: we check the counting array at index 2: [0, 1, 3, 5], and decrement it -> [0, 1, 2, 5], so 2 will go at index 2 in the output: [0, 0, 2, 0, 0] Second element [2, 3, 1, 3, 2]: we check the counting array at index 3: [0, 1, 2, 5], and decrement it -> [0, 1, 2, 4], so 3 will go at index 4 in the output: [0, 0, 2, 0, 3] Third element [2, 3, 1, 3, 2]: we check the counting array at index 1: [0, 1, 2, 4], and decrement it -> [0, 0, 2, 4], so 1 will go at index 0 in the output: [1, 0, 2, 0, 3] Fourth element [2, 3, 1, 3, 2]: we check the counting array at index 3: [0, 1, 2, 4], and decrement it -> [0, 0, 2, 3], so 3 will go at index 3 in the output: [1, 0, 2, 3, 3] Fifth element [2, 3, 1, 3, 2]: we check the counting array at index 2: [0, 0, 2, 4], and decrement it -> [0, 0, 1, 3], so 2 will go at index 1 in the output: [1, 2, 2, 3, 3] The output array is now sorted and can be returned as is. Note: - you can assume the input will only include positive numbers
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;
}
}
![The idea behind counting sort is to keep track of the counts of each element in the
array, then use those counts to recreate the array in sorted order. For example, if you
know the input array has 2 tens in it and 3 elements less than 10, then you can
conclude that the sorted array will look like this: [x, x, x, 10, 10, ...]. In other words you
know that a 10 must go at index 4, and a 10 must go at index 3. Counting sort is one
sort that uses this concept to sort all elements in an array.
These are videos that show you how Counting Sort works: 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.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F5483afab-7850-40f6-959f-e698dea1419a%2Fbd036467-92d7-4090-8f17-09728fa04555%2Fcvun5fa_processed.png&w=3840&q=75)
![The steps to counting sort are:
-
Find the max element in the input array.
-
-
-
Create a counting array with size equal to the max element + 1. Now each index
of the array serves as a separate counter.
Iterate through the input array, and for each element, increment the
corresponding index in the counting array by 1. For example, if the input array is
[2, 3, 1, 3, 2] the counting array will be updated as follows:
First element [2, 3, 1, 3, 2]: Increment the value at index 2, resulting in [0, 0, 1, 0]
Second element [2, 3, 1, 3, 2]: Increment the value at index 3, resulting in [0, 0, 1, 1]
Third element [2, 3, 1, 3, 2]: Increment the value at index 1, resulting in [0, 1, 1, 1]
Fourth element [2, 3, 1, 3, 2]: Increment the value at index 3, resulting in [0, 1, 1, 2]
Fifth element [2, 3, 1, 3, 2]: Increment the value at index 2, resulting in [0, 1, 2, 2]
Modify the counting array to be a "running total". Meaning the value at an index
k will be the count of elements in the input array that were less than or equal to
k. Using the example array from above: [2, 3, 1, 3, 2], you would get a counting
array: [0, 1, 3, 5]
Input: [0, 1, 2, 2]
Output: 0, 0+1; 0+1+2; 0+1+2+2 producing [0, 1, 3, 5]
Create an output array the same size as the input array.
Iterate through the input array again, for each element reduce its count in the
counting array by 1, then place the element at that index in the output array, for
example with an input array of [2, 3, 1, 3, 2] the iterations would be as follows:
First element [2, 3, 1, 3, 2]: we check the counting array at index 2: [0, 1, 3, 5], and
decrement it -> [0, 1, 2, 5], so 2 will go at index 2 in the output: [0, 0, 2, 0, 0]
Second element [2, 3, 1, 3, 2]: we check the counting array at index 3: [0, 1, 2, 5], and
decrement it -> [0, 1, 2, 4], so 3 will go at index 4 in the output: [0, 0, 2, 0, 3]
Third element [2, 3, 1, 3, 2]: we check the counting array at index 1: [0, 1, 2, 4], and
decrement it -> [0, 0, 2, 4], so 1 will go at index 0 in the output: [1, 0, 2, 0, 3]
Fourth element [2, 3, 1, 3, 2]: we check the counting array at index 3: [0, 1, 2, 4], and
decrement it -> [0, 0, 2, 3], so 3 will go at index 3 in the output: [1, 0, 2, 3, 3]
Fifth element [2, 3, 1, 3, 2]: we check the counting array at index 2: [0, 0, 2, 4], and
decrement it -> [0, 0, 1, 3], so 2 will go at index 1 in the output: [1, 2, 2, 3, 3]
The output array is now sorted and can be returned as is.
Note:
-
you can assume the input will only include positive numbers](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F5483afab-7850-40f6-959f-e698dea1419a%2Fbd036467-92d7-4090-8f17-09728fa04555%2Fpsb038c_processed.png&w=3840&q=75)
Step by step
Solved in 2 steps with 1 images
