DEV Community

Dumb Down Demistifying Dev
Dumb Down Demistifying Dev

Posted on • Updated on

Counting Sort

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;
}
Enter fullscreen mode Exit fullscreen mode

Discussion (0)