preface

Reading “learning JavaScript data structure and algorithm (3rd edition)” have a feeling that I hope every time learning algorithm can output a blog, income column, check their own learning situation ~ article has a mistake welcome various big god correction, don’t spray, if you want to spray, trouble light, thank you ~

start

Counting sort is a non-comparison sorting algorithm. It is a distributed sorting algorithm, which uses auxiliary data structures (called buckets) that have been organized to get sorted arrays. It is an excellent algorithm for sorting integers (it is an integer sorting algorithm), sorting integers in a range of time complexity O(n+k), where K is the size of the temporary count array; But it does require more memory to hold temporary arrays, which is a trade off of space for time. It has the complexity of (n+k) (where k is the range of integers), and is faster than any comparison sorting algorithm. And when O(k)>O(nlog(n)), its efficiency is not as good as that based on comparison (the time complexity of comparison based on the theoretical lower limit is O(nlog(n)), such as merge sort, heap sort).

Train of thought

For example arrays [0, 1, 1, 3, 5, 5, 7, 8]

• We associate the index of the count array with the value of the original array. The counter array subscript 0 corresponds to the array value 0 in the original array. The maximum value of the subscript of the counter array corresponds to the maximum value of the original array.

• Find the maximum n in the original array and create a count array of length n+1. (array subscript range: 0 ~ n), then the length of the array is n+1, then the length of the count array is 8 +1 = 9.

• Count array generation, count the number of values in the original array.

• Once the count array is generated, we can restore the sorted array. The subscript of the counter array records the occurrence of the value in the original array, and the value of the counter array records the occurrence of the value in the original array. For example, if the counter array is [3, 4, 1], then it restores the sorted array to be [0, 0, 0, 1, 1, 1, 2].

See the following code explanation

implementation

function countingSort(array) {
  if (array.length <= 1) return array;
  var maxValue = findMaxValue(array); // Find the maximum N in the original array, then create a count array of length N+1, because to access array[N], the array must be at least N+1
  // var maxValue = Math.max(... array); // Select * from ES6
  var counts = new Array(maxValue + 1); // An array for counting
  // Iterate over the array and store the element count into the count array
  array.forEach(element= > {
    if(! counts[element]) counts[element] =0 // If there is no value, set the number of values to 0
    counts[element]++; // Make the number of values in the index +1
  });

  let sortIndex = 0; // Secondary index
  // Start sorting the array, since the index is as large as the maximum value, so the corresponding I is the value of the original array array,
  // Assign directly to array[sortIndex] where the whlie loop continues incrementing if there are multiple equal counts
  counts.forEach((count, i) = > {
    while(count > 0){
      array[sortIndex++] = i; //
      count--; // The number of elements in the array -- when 0, jump out of while to continue forEach}})return array;
}

// Find the maximum value in the array
function findMaxValue(array) {
  var max = array[0];
  for (let i = 0; i < array.length; i++) {
    if (array[i] > max) {
      max = array[i]
    }
  }
  return max
}

var arr = [1.0.5.1.3.8.5.7]
console.log(countingSort(arr)) // [0, 1, 1, 3, 5, 5, 7, 8]
Copy the code

The results of

To optimize the

The above code is a bit of a problem

1. If the array has negative integers
2. If the maximum value in the array is 999, and the value in the array is between 990 and 999, then creating an array of length 1000 is a huge waste of space

Count [0] = 990. Then count [0] = max-min + 1

function countingSort2(array) {
  // Find the maximum and minimum values in the original array
  var maxValue = Math.max(... array);// Select * from ES6
  var minValue = Math.min(... array);var counts = new Array(maxValue - minValue + 1); // Create count array

  // Generate count array
  array.forEach((element,i) = > {
    // Index + minValue = value
    var index = array[i] - minValue;
    if(! counts[index]) counts[index] =0;
    counts[index]++;
  })

  // Restore the sorted array from the count array
  var sortedIndex = 0;
  counts.forEach((count, i) = > {
    while (count > 0) {
      array[sortedIndex++] = i + minValue; // The association is: I + minValue = valuecount--; }})return array;
}
var arr2 = [1, -1, -2.1.0.0.3.1.3.5.2]
console.log(countingSort2(arr2)) // [-2, -1, 0, 0, 1, 1, 1, 2, 3, 3, 5]
Copy the code

The complexity of the

• Time complexity

Counting sort is suitable for integer sort, and the time complexity is O(n+ K). Just a quick explanation of why it’s order n plus k. The outer layer of the loop is determined by the length of the counts — the difference between the highest values of the array (denoted as k). The while loop is determined by the count, and the sum of all counts is exactly the length of the array (denoted as n).

• Spatial complexity

The implementation in the code has space complexity O(k). So you can see that when k is really large, you’re going to use a lot of space.

other

# # front-end algorithm learning – the complexity of algorithm front end will algorithm (a) : bubble sort # front-end will algorithm (2) : selection # front-end will algorithm (3) : insertion sort # front-end will algorithm (4) : merge sort # front-end will algorithm (5) : quick sort # front-end will algorithm (6) : hill sorting

The last

Dregs a, welcome all great god many correction, not praise, just supervision correction

reference

# Write the algorithm and remember it: Counting sort