Visualize Counting Sort as it counts values and places them into sorted order.
Counting Sort is a non-comparison-based sorting algorithm that works by counting the number of occurrences of each value and using those counts to place elements into the correct position.
function countingSort(arr) {
const max = Math.max(...arr);
const count = new Array(max + 1).fill(0);
const output = new Array(arr.length);
arr.forEach((value) => {
count[value] += 1;
});
for (let i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
for (let i = arr.length - 1; i >= 0; i--) {
const value = arr[i];
output[count[value] - 1] = value;
count[value] -= 1;
}
return output;
}
def counting_sort(arr):
if not arr:
return []
maximum = max(arr)
count = [0] * (maximum + 1)
output = [0] * len(arr)
for value in arr:
count[value] += 1
for i in range(1, len(count)):
count[i] += count[i - 1]
for value in reversed(arr):
output[count[value] - 1] = value
count[value] -= 1
return output
public static int[] countingSort(int[] arr) {
int max = Arrays.stream(arr).max().orElse(0);
int[] count = new int[max + 1];
int[] output = new int[arr.length];
for (int value : arr) {
count[value]++;
}
for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
for (int i = arr.length - 1; i >= 0; i--) {
int value = arr[i];
output[count[value] - 1] = value;
count[value]--;
}
return output;
}
1. What is the main advantage of Counting Sort compared to comparison-based sorts?
2. Which step comes first in the Counting Sort algorithm?
3. Why does Counting Sort compute a prefix sum over the count array?
4. What is a key limitation of Counting Sort?
5. During placement, why does Counting Sort iterate the input array in reverse order?