What do we understand about Counting Sort?
- One of the most effecient sorting algorithm
- Has at least 3 loops to be implemented
- Should be implemented mathematically
- Is NOT a comparison sort
- ONLY Interger values from negative to positive
- Stable algorithm
- Returns a new Array
- Time complexity
- Best is O(n+k)
- Average is O(n+k)
- Worst is O(n+k)
- Space complexity
- O(k)
function CountingSort(arr) {
let max = arr[0];
let min = arr[0];
arr.forEach(val => {
if (val > max) max = val;
if (val < min) min = val;
});
//! to account for negative numbers, we use max and min.
//! e.g. 10 - (-4) = 14 Array size.
//! we need a +1 position to the right for counting of left & right values
let counter_size = max - min + 1;
let counter = new Array(counter_size).fill(0);
//! the index of counter Array indicates the value of the number in arr Array
//! count the number of times the number repeats and store in index of counter Array
arr.forEach((_, i) => counter[arr[i] - min]++);
//! to get the starting position of the number from arr Array,
//! count the previous value with current value of counter Array
for (let i = 1; i < counter.length; i++) {
counter[i] += counter[i - 1];
}
let results = new Array(arr.length);
//! skip the last element as it is not used in the result
for (let i = results.length - 1; i >= 0; i--) {
//! decrement the counter before assigning value to results Array of the index position
//! assign results Array with original Array value at position i
results[--counter[arr[i] - min]] = arr[i];
}
return results;
}
Top comments (0)