This is the 19th day of my participation in the Genwen Challenge

What is counting sort

Counting sort, as it’s called, is sorting by counting, or counting the number of times each element is repeated.

As mentioned above, the original sequence has five values, ranging from 1 to 5.

// The original sequence
let arr = [5.4.3.2.3.1]
Copy the code

So, the values of these integers must be one, two, three, four, five.

So based on the range of integers, we can create an array of length 6 (including 0, so length 6) with subscripts from 0 to 5, all elements starting with 0.

// An array of 6 counts with initial values all 0
let countingArr = [0.0.0.0.0.0]
Copy the code

It is then added to the count array according to the number and order of occurrences of elements in the original sequence.

// An array of 6 counts with initial values all 0
let countingArr = [0.0.0.0.0.0]
// If the first element of the original array is 5, increment the index 5 in the count array by 1
countingArr[5] + =1
// If the second element of the original array is 4, we increment the subscript 4 in the count array by 1
countingArr[4] + =1
// If the third element of the original array is 3, then the subscript 3 of the count array is incremented by 1
countingArr[3] + =1
// If the fourth element of the original array is 2, increment 1 at the subscript 2 of the count array
countingArr[2] + =1
// If the fifth element of the original array is 3, increment 1 at the subscript 3 of the count array
countingArr[3] + =1
// If the sixth element of the original array is 1, increment 1 at the subscript 1 of the count array
countingArr[1] + =1
// The final count array is as follows
console.log(countingArr)
/ /,1,1,2,1,1 [0]

Copy the code

We get the count array, the statistics, and sorting is easy.

The next step is to iterate through the array, printing out the subscript value of the element, as many times as the value of the element.

// Count the sorting result
let result = [1.2.3.3.4.5]
Copy the code

conclusion

Counting sort sorting algorithm is the use of space, in time, while using it sort of fast, but when the interpolation between the sequence of maximum minimum gap is too large, the total discomfort sort (assuming that 20 random Numbers, numerical range from 0 to 1 billion, you need to open 1 billion array space, not only a waste of space, and the time complexity is high). Second, count sort is only suitable for integer sequence element scenarios, because count sort itself cannot count decimals.

Code implementation

/** * find the largest item in the array *@param {array} Array Specifies the maximum number of arrays to operate on@param {function} CompareFn // Compare with defaultCompare * by default@returns {number}} returns the maximum value found in the array */
export function findMaxValue(array, compareFn = defaultCompare) {
  // To find the maximum value in the array, we simply iterate over and find the item with the maximum value
  if (array && array.length > 0) { 
    let max = array[0]; 
    for (let i = 1; i < array.length; i++) {
      if(compareFn(max, array[i]) === Compare.LESS_THAN) { max = array[i]; }}return max;
  }
  return undefined;
}
/** * count sort *@param {array} Array Array to be sorted *@returns {array} Returns the sorted array */
export function countingSort(array) {
  if (array.length < 2) { // If the array to be sorted is empty or has only one element, there is no need to run the sorting algorithm.
    return array;
  }
  const maxValue = findMaxValue(array); // Find the maximum value in the array
  let sortedIndex = 0;
  const counts = new Array(maxValue + 1); // Create count array from index 0 up to maximum index value + 1
  array.forEach(element= > {
    // Iterate over each position in the array and increment the element count in the COUNTS array
    if(! counts[element]) {// To ensure the increment succeeds, if the position used to count an element in the counts array is not initially initialized with 0
      counts[element] = 0; // We assign it to 0
    }
    counts[element]++;
  });
  // console.log('Frequencies: ' + counts.join());
   // After all elements are counted, we iterate through the COUNTS array and build the sorted result array
  counts.forEach((element, i) = > {
    while (element > 0) {
      array[sortedIndex++] = i; Since there may be multiple elements with the same value, we add the elements according to the number of occurrences in the original array
      element--; // Decrease the count until it is 0}});return array;
}
Copy the code