This article is a translation of Swift Algorithm Club.

Swift Algorithm Club is an open source project produced by Raywenderlich.com to realize algorithms and data structures by Swift. Currently, there are 18000+⭐️ on GitHub. I have made a brief statistics, and there are about 100 algorithms and data structures. It’s basically a good resource for iOSer learning algorithms and data structures.

🐙andyRon/ swift-algorithm-club-CN is my project of learning and translating for Swift Algorithm Club. Due to the limited capacity, if you find any errors or improper translation, please correct them. Welcome to Pull Request. Also welcome interested, have time partners to participate in translation and learning 🤓. Of course, we welcome ⭐️, 🤩🤩 ️ ⭐ ⭐.

You can see 🐙swift-algorithm-club-cn/Counting Sort for the translation of this article and the code

Counting Sort

Counting sort is an algorithm for sorting a collection of objects according to keys that are small integers. It operates by counting the number of objects that have each distinct key values, and using arithmetic on those counts to determine the positions of each key value in the output sequence. Counting sort is an algorithm that sorts a collection of objects by small integer keys. Operate by counting the number of objects with each different key value and using arithmetic on these counts to determine the position of each key value in the output sequence.

example

To understand the algorithm, let’s look at a small example.

Consider arrays: [10, 9, 8, 7, 1, 2, 7, 3]

The first step:

The first step is to count the total number of occurrences of each item in the array. The output of the first step will be a new array, as follows:

Index 0 1 2 3 4 5 6 7 8 9 10
Count 0 1 1 1 0 0 0 2 1 1 1
Copy the code

The maximum value of this Index corresponds to the maximum value in the array, 10.

Here is the code that completes the first step:

  let maxElement = array.max()??0

  var countArray = [Int](repeating: 0.count: Int(maxElement + 1))
  for element in array {
    countArray[element] += 1
  }
Copy the code

The second step:

In this step, the algorithm tries to determine the number of elements placed before each element. The total number of occurrences of each element has been known through the first step, which can be obtained. Add the previous count and the current count to each index (countArray[index] + countArray[index-1]).

The count array looks like this:

Index 0 1 2 3 4 5 6 7 8 9 10
Count 0 1 2 3 3 3 3 5 6 7 8
Copy the code

The code for step 2:

  for index in 1 ..< countArray.count {
    let sum = countArray[index] + countArray[index - 1]
    countArray[index] = sum
  }
Copy the code

The third step

This is the last step of the algorithm. Each element in the original array is placed in the position defined by the output of the second step. For example, the number 10 will be placed at index 7 in the output array. In addition, when you place elements, you need to reduce the count by one because many elements are removed from the array.

The final output is:

Index  0 1 2 3 4 5 6 7
Output 1 2 3 7 7 8 9 10
Copy the code

Here is the code for the last step:

  var sortedArray = [Int](repeating: 0.count: array.count)
  for element in array {
    countArray[element] -= 1
    sortedArray[countArray[element]] = element
  }
  return sortedArray
Copy the code

performance

The algorithm uses a simple loop to sort the set. Therefore, the time to run the entire algorithm is **O(n+k), where O(n)** represents the loop required to initialize the output array and **O(k)** is the loop required to create the count array.

The algorithm uses arrays of length N + 1 and n, so the total space required is O(2n). Thus, it saves space for a set of keys scattered along a digital line in a dense area.

Translated by Ali Hafizji and proofread by Andy Ron

Supplement after translation

Counting sort assumes that each of the n input elements is an integer between 0 and k, where k is some integer. When k=O(n), the running time of sort is θ (n).

The idea of counting sort is that for each input element, count the number of elements less than it, and if there are 10 elements less than it, it should be placed at position 11, and if there are 17 elements less than it, it should be placed at position 18. This scheme needs to be modified slightly when several elements are the same because they cannot be placed in the same output position. The figure below (from Introduction to Algorithms) shows the actual operation.

Construct an auxiliary array C of length k. After traversing A for the first time, the number of occurrences of each number in the interval [0,k] is obtained, and these times are written into C to obtain the result of Figure (A). Then, each element in C is transformed into the sum of all previous elements to obtain the result of Figure (b). Next, the sequence A is traversed from back to front again, and the value of the corresponding subscript in C is searched according to the extracted element, and then the value is used as the subscript to find the position in B, that is, the sorted position of the element. For example, if the last element of A is 3, find that C[3] is 7, set B[7]=3, and incidentally subtract C[3] by one to prevent the same number from being placed in the same place.

The time cost of counting sort can be calculated as follows: the time to traverse A and calculate C for the first time is θ (n), the time to accumulate C is θ (k), and the time to traverse A again and assign to B is θ (n), so the total time is θ (k + n). In practice, we usually use counting sort when k=O(n), and the running time is θ (n).

reference

www.jianshu.com/p/ff1797625…