Thuật toán Counting Sort (Sắp xếp đếm)

Counting Sort là thuật toán sắp xếp ổn định (stable), dùng để sắp xếp đối tượng theo khóa là số nhỏ. Nó đếm số lần xuất hiện của mỗi giá trị khóa. Hiệu quả khi chênh lệch giữa các khóa không quá lớn, nếu không sẽ tăng độ phức tạp không gian.

Độ phức tạp Counting Sort

• Time Complexity: O(n + r) (r = range = max - min + 1)
• Space Complexity: O(n + r)

Input và Output

Input: Danh sách chưa sắp xếp: 2 5 6 2 3 10 3 6 7 8
Output: Mảng trước sắp xếp: 2 5 6 2 3 10 3 6 7 8
Mảng sau sắp xếp: 2 2 3 3 5 6 6 7 8 10

Thuật toán

countingSort(array, size)
Input: Mảng dữ liệu, tổng số phần tử
Output: Mảng đã sắp xếp

Begin
  max = lấy phần tử lớn nhất từ mảng
  định nghĩa mảng count kích thước [max+1]
  for i := 0 to max do count[i] = 0 done
  for i := 1 to size do tăng count[array[i]] done
  for i := 1 to max do count[i] = count[i] + count[i-1] done (tần suất tích lũy)
  for i := size down to 1 do
    output[count[array[i]]] = array[i]
    count[array[i]] -= 1
  done
  return output array
End

Ví dụ (C++)

#include <iostream>
#include <algorithm>
using namespace std;

void display(int *array, int size) {
    for(int i = 1; i <= size; i++) cout << array[i] << " ";
    cout << endl;
}

int getMax(int array[], int size) {
    int max = array[1];
    for(int i = 2; i <= size; i++)
        if(array[i] > max) max = array[i];
    return max;
}

void countSort(int *array, int size) {
    int output[size+1];
    int max = getMax(array, size);
    int count[max+1];
    for(int i = 0; i <= max; i++) count[i] = 0;
    for(int i = 1; i <= size; i++) count[array[i]]++;
    for(int i = 1; i <= max; i++) count[i] += count[i-1];
    for(int i = size; i >= 1; i--) {
        output[count[array[i]]] = array[i];
        count[array[i]]--;
    }
    for(int i = 1; i <= size; i++) array[i] = output[i];
}

int main() {
    int n; cout << "Nhập số phần tử: "; cin >> n;
    int arr[n+1];
    cout << "Nhập phần tử:" << endl;
    for(int i = 1; i <= n; i++) cin >> arr[i];
    cout << "Trước sắp xếp: "; display(arr, n);
    countSort(arr, n);
    cout << "Sau sắp xếp: "; display(arr, n);
}

Kết quả

Nhập số phần tử: 10
Nhập phần tử: 2 5 6 2 3 10 3 6 7 8
Trước sắp xếp: 2 5 6 2 3 10 3 6 7 8
Sau sắp xếp: 2 2 3 3 5 6 6 7 8 10

Đặc điểm: Counting Sort ổn định, không so sánh, chỉ dùng cho số nguyên không âm (hoặc có thể điều chỉnh cho số âm bằng offset). Hiệu quả khi range nhỏ (r = O(n)).