Bỏ qua

Sắp xếp đếm

前置知识：前缀和

Nhắc nhở

Trang này không nói về Sắp xếp theo cơ số (Radix sort).

Trang này sẽ giới thiệu ngắn gọn về Sắp xếp đếm (Counting sort).

Định nghĩa

Sắp xếp đếm (tiếng Anh: Counting sort) là một thuật toán sắp xếp có độ phức tạp tuyến tính.

Quy trình

Nguyên lý của sắp xếp đếm là sử dụng một mảng phụ \(C\), trong đó phần tử thứ \(i\) lưu số lần xuất hiện của giá trị \(i\) trong mảng \(A\) cần sắp xếp, sau đó dựa vào mảng \(C\) để đưa các phần tử của \(A\) về đúng vị trí.1

Quy trình gồm ba bước:

  1. Đếm số lần xuất hiện của từng số;
  2. Tính tổng tiền tố (prefix sum) của số lần xuất hiện;
  3. Dựa vào tổng tiền tố, từ phải sang trái xác định thứ hạng của từng số.

Vì sao cần tính tổng tiền tố?

Nếu chỉ đơn giản đưa các số có \(C[i]>0\) vào mảng \(A\) theo thứ tự, sẽ không xử lý được trường hợp có nhiều số trùng nhau.

Bằng cách tính tổng tiền tố cho từng phần tử của mảng phụ \(C\), ta xác định được thứ hạng duy nhất cho từng phần tử trùng nhau:

Giá trị tại mỗi vị trí của \(C\) là số lượng phần tử có giá trị đó, còn tổng tiền tố tại vị trí đó là thứ hạng của phần tử trùng cuối cùng.

Nếu ta duyệt \(A\) từ phải sang trái, mảng kết quả sẽ giữ nguyên thứ tự ban đầu của các phần tử trùng nhau, tức là thuật toán ổn định.

counting sort animate example

Tính chất

Tính ổn định

Sắp xếp đếm là một thuật toán ổn định.

Độ phức tạp thời gian

Độ phức tạp thời gian của sắp xếp đếm là \(O(n+w)\), trong đó \(w\) là miền giá trị của dữ liệu cần sắp xếp.

Cài đặt mã nguồn

Giả mã

\[ \begin{array}{ll} 1 & \textbf{Input. } \text{Một mảng } A \text{ gồm }n\text{ số nguyên dương không vượt quá } w. \\ 2 & \textbf{Output. } \text{Mảng }A\text{ sau khi được sắp xếp tăng dần, ổn định.} \\ 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

Tài liệu tham khảo & chú thích

  1. Counting sort - Wikipedia (tiếng Trung) ↩

Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:OI-wiki
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply