Counting sort

Categories :

Problem:

With a small range of input values, try to find out the frequecy and sort the input values.

Concept:

Assume the values in the array are within 0-99.

First, we can create an array with size 100 to store the frequency of the numbers and initialize the values to 0.

Next, we use for-loop to loop through the input array and add the frequecy counter of the appeared numbers by 1.

Then, we loop through the frequecy counter and output the number to the array if the frequecy is higher than 0.

Finally, we return the array.

Javascript code snippet:

function countingSort(arr) {
  const count = Array(100).fill(0);
  let j = 0;
  for (i=0; i<count.length; i++) {
     count[arr[i]] = count[arr[i]] + 1;
  }
  for (i=0; i < 100; i++)
 {
     while (count[i] > 0)
 {
       arr[j] = i;
       j++;
       count[i] = count[i] - 1;
     }
  }
  return arr;
}

Leave a Reply

Your email address will not be published. Required fields are marked *