I have two implementation variation for countingSort algorithm.
#1 – Using an array to count the occurrences:
const countingSort1 = (arr) => {
const max = Math.max(...arr);
const count = new Array(max + 1).fill(0);
for (let i = 0; i < arr.length; i++) {
count[arr[i]]++;
}
console.log(count); // Array(120001) [0, 0, 0, 1, 0, 1, 0, 0, 0, 0, …]
let k = 0;
for (let i = 0; i < count.length; i++) {
for (let j = 0; j < count[i]; j++) {
arr[k] = i;
k++;
}
}
return arr;
};
#2 – Using a dictionary (object) to count the occurrences:
const countingSort2 = (arr) => {
const count = {};
for (let i = 0; i < arr.length; i++) {
const curr = arr[i];
count[curr] = (count[curr] ?? 0) + 1;
}
console.log(count); // Object {3: 1, 5: 1, 24599: 1, 120000: 1}
let i = 0;
for (let val in count) {
for (let j = 0; j < count[val]; j++) {
arr[i] = +val;
i++;
}
}
return arr;
};
Usage:
const numbers = [3, 5, 24599, 120000];
console.log(countingSort1(numbers)); // [3, 5, 24599, 120000]
console.log(countingSort2(numbers)); // [3, 5, 24599, 120000]
Want to know:
When we have a wide range of numbers to sort with counting sort, the size of the counting array becomes very large, which can lead to memory issues.
This is correct because, as you can see, our range is from 3 to 120000, and the implementation shown in countingSort1()
creates an array sized 120001 to accommodate all possible values. However, this is not the case in the second implementation, countingSort2()
.
So why do we talk about a ‘wide range’ (I know, more unique elements = more memory), and why is the countingSort1()
style of implementation used more widely than countingSort2()
? What are the drawbacks of using countingSort2()
?