Skip to content

Counting Sort

Note

This page introduces Counting Sort, not Radix Sort.

This page briefly introduces Counting Sort.

Definition

Counting sort (English: Counting sort) is a linear-time sorting algorithm.

Process

Counting sort works by using an auxiliary array \(C\), where the \(i\)-th element is the number of elements in the input array \(A\) whose value equals \(i\). Then, based on array \(C\), the elements in \(A\) are placed in the correct positions.1

Its process is divided into three steps:

  1. Count the frequency of each number;
  2. Compute the prefix sum of the frequencies;
  3. Use the prefix sum of frequencies to determine the rank of each number from right to left.

Reason for Computing Prefix Sum

Directly placing elements from \(C\) into \(A\) in order of positive values cannot handle duplicate elements.

By computing the prefix sum for each entry in the auxiliary array \(C\), combined with the value of each entry, we can assign a unique rank to duplicate elements:

The value of each entry in the auxiliary array \(C\) is the count of duplicate elements for that key, and the prefix sum of that entry is the rank of the last duplicate element.

If we process \(A\) in reverse order, the sorted array will preserve the original order of \(A\) (for identical key values), resulting in a stable sorting algorithm.

counting sort animate example

Properties

Stability

Counting sort is a stable sorting algorithm.

Time Complexity

The time complexity of counting sort is \(O(n+w)\), where \(w\) represents the range of values in the input data.

Code Implementation

Pseudocode

\[ \begin{array}{ll} 1 & \textbf{Input. } \text{An array } A \text{ consisting of }n\text{ positive integers no greater than } w. \\ 2 & \textbf{Output. } \text{Array }A\text{ after sorting in nondecreasing order stably.} \\ 3 & \textbf{Method. } \\ 4 & \textbf{for }i\gets0\textbf{ to }w\\ 5 & \qquad \textit{cnt}[i]\gets0\\ 6 & \textbf{for }i\gets1\textbf{ to }n\\ 7 & \qquad \textit{cnt}[A[i]]\gets\textit{cnt}[A[i]]+1\\ 8 & \textbf{for }i\gets1\textbf{ to }w\\ 9 & \qquad \textit{cnt}[i]\gets \textit{cnt}[i]+\textit{cnt}[i-1]\\ 10 & \textbf{for }i\gets n\textbf{ downto }1\\ 11 & \qquad B[\textit{cnt}[A[i]]]\gets A[i]\\ 12 & \qquad \textit{cnt}[A[i]]\gets \textit{cnt}[A[i]]-1\\ 13 & \textbf{return } B \end{array} \]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
#include <cstring>
constexpr int MAXN = 1010;
constexpr int MAXW = 100010;

int cnt[MAXW], b[MAXN];

int* counting_sort(int* a, int n, int w) {
  memset(cnt, 0, sizeof(cnt));
  for (int i = 1; i <= n; ++i) ++cnt[a[i]];
  for (int i = 1; i <= w; ++i) cnt[i] += cnt[i - 1];
  for (int i = n; i >= 1; --i) b[cnt[a[i]]--] = a[i];
  return b;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def counting_sort(a, n, w):
    b = [0] * n
    cnt = [0] * (w + 1)
    for i in range(1, n + 1):
        cnt[a[i]] += 1
    for i in range(1, w + 1):
        cnt[i] += cnt[i - 1]
    for i in range(n, 0, -1):
        b[cnt[a[i]] - 1] = a[i]
        cnt[a[i]] -= 1
    return b

References and Notes

  1. Counting sort - Wikipedia ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用