What is counting sort?

Counting sort is not a sorting algorithm based on comparison. Its core is to store the input data value as the key in the additional array space. As a sort of linear time complexity, counting sort requires that the input data must be integers with a definite range

The most important thing about counting sort is that you specify integers in the range, say, 0 to 10, so the value in the array has to be between 0 and 10

chestnuts

Sequence: 9,3,5,4,9,1,2,7,8,1,3,6,5,3,4,0,10,9, 7,9

First determine that the range of the sequence is 0-10, and list the sequence of the range, as shown in Figure 1

For example, if the first integer is 9, then the element with index 9 in the array is added 1

<img src=”https://noxussj.top:3000/28/1.png”></img>

Figure 1

If the second integer is 3, then add 1 to the elements of the array index 3, as shown in Figure 2

<img src=”https://noxussj.top:3000/28/2.png”></img>

Figure 2

And so on…

After the completion of the final traversal, the state is as follows, as shown in Figure 3

<img src=”https://noxussj.top:3000/28/3.png”></img>

Figure 3

The value of each index position in the array, which represents the number of occurrences of the corresponding integer in the sequence

With this “statistical result”, sorting is simple. Just traverse the array and print the subscript value of the element. The number of times the element is printed

0, 1, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 8, 9, 9, 9, 10

The final output sequence is already sorted

<img src=”https://noxussj.top:3000/28/4.gif”></img>

At this point somebody might ask, what if the minimum value of the sequence doesn’t start at 0?

This is the time to calculate the offset

How do I calculate the offset?

Take the minimum value of the sequence as the offset. If the minimum value is 90, then the index of the statistic array corresponding to the integer 95 is 95-90 = 5

<img src=”https://noxussj.top:3000/28/5.png”></img>

Comics: What is counting sort?

additional

  • This article is published through multiple platforms of “We Media” and will not be maintained after publication. If you have any objection to the content, you can discuss it in the GitHub below
  • The ongoing maintenance / 500 + face questions before update/notes 】 https://github.com/noxussj/In…
  • [3D city modeling using three. JS (Zhuhai City)] https://3d.noxussj.top/