Have you ever had a classic algorithm that you thought was clear in the class, but forgot after a while?

This series of articles attempts to address that question.

Read up on the sorting algorithms, read up on their names, and they’re all very aptly named.

For example, counting sort, the so-called “counting”, is to count, count the number of times each element repeated.

The figure above illustrates the overall flow of the algorithm. It is divided into two steps: check and row.

Start by looking at how many occurrences of each element, such as element 0 once, element 1 once, element 2 three times, etc.

Now that we’re done, the sorting process is easy. You can fill the array from small to large, just as many times as it appears. The word “from small to large” embodies the process of sorting.

Counting sort is, in my opinion, the simplest and most intuitive of all sorting algorithms. Search and platoon, both of which are easy to implement.

Query, the implementation is as follows:

let array = [3.2.1.2.3.2.0.4]
let counts = []
for (let v of array) {
  counts[v] = (counts[v] || 0) + 1
}
console.log(counts) // [1, 1, 3, 2, 1]
Copy the code

The COUNTS array is the statistical result with its subscript representing the elements of the array to be sorted. Its length is 5 (the maximum size of the array to be arrayed plus 1).

Row, implement as follows:

let result = []
for (let i = 0; i < counts.length; i++) {
  let count = counts[i]
  while(count > 0) {
    result.push(i)
    count--
  }
}
console.log(result) // [0, 1, 2, 2, 2, 3, 3, 4]
Copy the code

In the code above, result is a new array. Of course, you can also fill it with array, which requires a variable to keep track of where it is ranked. See the full implementation link at the end of this article.

It can be seen from the algorithm process that counting sort is suitable for integer sort. So here’s the question, what if there’s a negative number?

And the way to do that, it’s easy to imagine, is let’s just go through and find the smallest value in the array, and use that as the offset.

If the data is [-3, -2, -1, -2, -3, -2, 0, -4], the minimum value of the array in the data is -4, and the maximum value is 0. We’ll just use the 0th subscript of COUNTS for the minimum value.

let array = [- 3.2 -.- 1.2 -.- 3.2 -.0.4 -]
let counts = [], result = []
let min = Math.min(... array)for (let v of array) {
  counts[v-min] = (counts[v-min] || 0) + 1
}
for (let i = 0; i < counts.length; i++) {
  let count = counts[i]
  while(count > 0) {
    result.push(i + min)
    count--
  }
}
console.log(result) // [-4, -3, -3, -2, -2, -2, -1, 0]
Copy the code

The offset is subtracted for statistics, and the offset is added back for sorting. Also, you can see that the length of counts is the difference between the maximum and minimum value plus 1.

This approach also avoids another problem, the waste of space in the data set. For example, if values are between 900 and 1000, then counts should only be 101 in length.

So far, the principle and implementation of counting sort have been described.

See the full code: codepen.

To sum up, counting sort is suitable for integer sort, with time complexity O(n+k). Just a quick explanation of why it’s order n plus k. Here we use a two-level loop. The outer layer is determined by the length of the counts — the difference between the highest values of the array to be counted (denoted as k). The while loop is determined by count, and the sum of all counts is exactly the length of the array (denoted as n). In addition, regarding the use of space, the space complexity of the initial implementation is O(n+ K), and the space complexity of the complete code is O(k). So you can see that when k is really large, you’re going to use a lot of space.

Counting sort, to be able to handwritten minutes, is the need to master its sorting principle. The first statistics of the number of occurrences, and then from small to large output, once understood is easy to write out, do not need to memorize.

Hope to help, the end of this article.


Articles in this series have been published:

  • Handwriting Algorithms and Remember it: Bubbling Sort
  • Handwriting Algorithms and Remembering them: Sorting by Choice
  • Handwriting Algorithms and Remembering them: Insertion Sort
  • Handwriting algorithm and Remember it: Merge Sort
  • “Handwriting algorithms and Memorizing them: QuickSort (Simple 5 Lines of Code)”
  • Handwriting Algorithms and Memorizing them: QuickSort (Easiest to Understand edition)