Count sort takes in a range of integers to be sorted. It uses the range of the integers (for example, the range of integers between 0 to 100), and counts the number of times each unique number appears in the unsorted input. This sorting technique is effective when the difference between different keys are not so big, otherwise, it can increase the space complexity.The counting sort algorithm is unique in that it can only be implemented on integers. This is part of what limits this algorithm’s usability.
function countsort(a) {
let minimum = a[0];
let maximum = a[0];
for(let i = 0; i < a.length; i++) {
if(a[i] < minimum)
minimum = a[i];
if(a[i] > maximum)
maximum = a[i];
}
for(let i=0;i < a.length;i++) {
a[i] -= minimum;
}
let bucket = [];
bucket.length = (maximum - minimum + 1);
for(let i = 0; i < bucket.length; i++){
bucket[i] = 0;
}
for(let i = 0; i < a.length; i++) {
bucket[a[i]]++;
}
let index = 0;
for(let i = 0; i < bucket.length; i++) {
if(bucket[i]==0) {
continue;
}
for(let j = 0; j < bucket[i]; j++) {
a[index++] = i+minimum;
}
}
return a;
}
Best Case : Ω (n+k)
Average Case : θ (n+k)
Worst Case: O (n+k)
O(k)
** where n is the length of the array and k is constant