DEV Community

Dumb Down Demistifying Dev
Dumb Down Demistifying Dev

Posted on • Edited on

4 4

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

Image of Datadog

Create and maintain end-to-end frontend tests

Learn best practices on creating frontend tests, testing on-premise apps, integrating tests into your CI/CD pipeline, and using Datadog’s testing tunnel.

Download The Guide

Top comments (0)

nextjs tutorial video

Youtube Tutorial Series 📺

So you built a Next.js app, but you need a clear view of the entire operation flow to be able to identify performance bottlenecks before you launch. But how do you get started? Get the essentials on tracing for Next.js from @nikolovlazar in this video series 👀

Watch the Youtube series

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay