Search…

Distribution Sort - Counting Sort

18/08/20203 min read
Distribution Sort - Counting Sort là sắp xếp bằng phép đếm phân phối. Đây là một thuật toán sắp xếp đơn giản cho trường hợp đặc biệt, các giá trị trong mảng cần sắp xếp đều là số nguyên và biết được giá trị của mảng nằm trong khoảng nào đó.

Counting Sort là 1 thuật toán sắp xếp bằng phép đếm phân phối (Distribution Counting Sort), đây là một trong những thuật toán sắp xếp rút ngắn được thời gian của quá trình thực hiện thuật toán.

Thuật toán Counting Sort

Counting Sort - Sắp xếp bằng phép đếm phân phối là 1 trong những giải thuật sắp xếp thuộc nhóm Distribution Sort. Đây là một thuật toán sắp xếp đơn giản cho trường hợp đặc biệt các giá trị trong mảng cần sắp xếp đều là số nguyên và biết được giá trị của mảng nằm trong khoảng nào đó. Ví dụ như [0..M], [3..N], …

Ý tưởng

Cho mảng cần sắp xếp các giá trị của mảng đều là số nguyên và thuộc khoảng [0..M].

Ý tưởng của thuật toán là đếm trong khoảng [0..M]:

  • Có bao nhiêu giá trị 0 (giả sử có C(0) giá trị).
  • Có bao nhiêu giá trị 1 (giả sử có C(1) giá trị),
  • Có bao nhiêu giá trị M (giả sử có C(M) giá trị).

Sau đó sắp xếp lại mảng bằng cách đặt C(0) phần tử 0 ở đầu, đặt C(1) phần tử 1 tiếp theo, … và đặt C(M) phần tử M cuối cùng.

Độ phức tạp của thuật toán này là O(max(N, M)). Giá trị của M càng nhỏ thì thuật toán sắp sếp càng nhanh.

Ví dụ

Cho dãy cần sắp xếp: 1, 4, 2, 7, 8, 2, 1, 3, 8, 6, 2, 4

Thì: C(1) = 2, C(2) = 3, C(3) = 1, C(4) = 2, C(6) = 1, C(7) = 1, C(8) = 2

  • Giá trị 1 đứng ở vị trí từ 1 → C(1), tức là từ 1 → 2.
  • Giá trị 2 đứng ở vị trí từ C(1) + 1 → C(1) + C(2), tức là từ 3 → 5.
  • ...
  • Tương tự giá trị i đứng ở vị trí từ C(1) + C(2) + C(3) + … + C(i - 1) + 1 → C(1) + C(2) + C(3) + … + C(i - 1) + C(i).

 Vậy dãy sau khi sắp xếp: 1 1 2 2 2 3 4 4 6 7 8 8

Hiện thực

void countingSort(int* input, int n)
{
    int countArr[SIZE] = { 0 };
 
    for (int i = 0; i < n; i++)
        countArr[input[i]]++;
 
    int outputIndex = 0;

    for (int j = 0; j < SIZE; j++)
        while (countArr[j]-- > 0)
            input[outputIndex++] = j;
}

Giải thích

Đếm số lần xuất hiện của mỗi phần tử.

for (int i = 0; i < INPUT_SIZE; i++)
    countArr[input[i]]++;

Sắp xếp lại dãy theo thuật toán.

for (int j = 0; j < SIZE; j++)
    while (countArr[j]-- > 0)
        input[outputIndex++] = j;

Code mẫu Counting Sort

#include <iostream>
using namespace std;
const int INPUT_SIZE = 20; const int SIZE = 20; void printArray(int *input, int n) { for (int i = 0; i < n; i++) cout << input[i] << "\t"; } void countingSort(int* input, int n) { int countArr[SIZE] = { 0 }; for (int i = 0; i < n; i++) countArr[input[i]]++; int outputIndex = 0; for (int j = 0; j < SIZE; j++) while(countArr[j]-- < 0) input[outputIndex++] = j; } int main() { int input[INPUT_SIZE] = { 2, 4, 6, 4, 7, 1, 4, 9, 5, 3, 7, 2, 2, 6, 9, 3, 7, 3, 4, 4 }; printArray(input, INPUT_SIZE); countingSort(input, INPUT_SIZE); printArray(input, INPUT_SIZE); return 0; }

Bài chung Series

IO Stream

IO Stream Co., Ltd

30 Trinh Dinh Thao, Hoa Thanh ward, Tan Phu district, Ho Chi Minh city, Vietnam
+84 28 22 00 11 12
developer@iostream.co

383/1 Quang Trung, ward 10, Go Vap district, Ho Chi Minh city
Business license number: 0311563559 issued by the Department of Planning and Investment of Ho Chi Minh City on February 23, 2012

©IO Stream, 2013 - 2024