Counting Sort – Thuật toán sắp xếp đếm phân phối

Counting sort là một thuật toán sắp xếp cực nhanh một mảng các phần tử mà mỗi phần tử là các số nguyên không âm; Hoặc là một danh sách các ký tự được ánh xạ về dạng số để sort theo bảng chữ cái. Counting sort là một thuật toán sắp xếp các con số nguyên không âm, không dựa vào so sánh. Trong khi các thuật toán sắp xếp tối ưu sử dụng so sánh có độ phức tạp O(nlogn) thì Counting sort chỉ cần O(n) nếu độ dài của danh sách không quá nhỏ so với phần tử có giá trị lớn nhất.

Ý tưởng của Counting sort

Hình ảnh dưới đây cho chúng ta thấy cách hoạt động của thuật toán sắp xếp này.

Bước 1:

Trong bước đầu tiên, chúng tôi đếm số lần xuất hiện của từng phần tử trong mảng cần sắp xếp A. Kết quả được lưu vào mảng C.

Counting Sort

Bước 2: Ở bước này, chúng ta cần xem xét sửa đổi giá trị của C. C[i] thể hiện giới hạn trên của chỉ số của phần tử i sau khi sắp xếp.

Bước 3: Duyệt qua từng phần tử của A và đặt nó vào đúng chỉ số của mảng chứa các giá trị đã sắp xếp B dựa vào C.

Cài đặt thuật toán Counting Sort

Code C:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>
 
// Function that sort the given input
void counting_sort(int input[], int n)
{
    int output[n]; // The output will have sorted input array
    int max = input[0];
    int min = input[0];
 
 int i;
    for(i = 1; i < n; i++)
    {
        if(input[i] > max)
            max = input[i]; // Maximum value in array
        else if(input[i] < min)
            min = input[i]; // Minimum value in array
    }
 
    int k = max - min + 1; // Size of count array
 
    int count_array[k]; // Create a count_array to store count of each individual input value
    for(i=0; i<k; i++)
        count_array[i]=0;
 
    for(i = 0; i < n; i++)
        count_array[input[i] - min]++; // Store count of each individual input value
 
    /* Change count_array so that count_array now contains actual
     position of input values in output array */
    for(i = 1; i < k; i++)
        count_array[i] += count_array[i - 1];
 
    // Populate output array using count_array and input array
    for(i = 0; i < n; i++)
    {
        output[count_array[input[i] - min] - 1] = input[i];
        count_array[input[i] - min]--;
    }
 
    for(i = 0; i < n; i++)
        input[i] = output[i]; // Copy the output array to input, so that input now contains sorted values
 
}
 
 
// Driver program to test above function
int main()
{
    int n = 9, i;
 
    int input[] = {1, 5, 2, 7, 3, 4, 4, 1, 5};
 
    counting_sort(input, n);
 
    printf("Sorted Array : ");
    for(i = 0; i < n; i++)
        printf("%d ", input[i]);
 
    return 0;
}
 
 
/* Output
Sorted Array : 1  1  2  3  4  4  5  5  7
*/

Code C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
// C++ implementation of Counting Sort
#include <iostream>
 
using namespace std;
 
// Function that sort the given input
void counting_sort(int input[], int n)
{
 
    int output[n]; // The output will have sorted input array
    int max = input[0];
    int min = input[0];
 
    for(int i = 1; i < n; i++)
    {
        if(input[i] > max)
            max = input[i]; // Maximum value in array
        else if(input[i] < min)
            min = input[i]; // Minimum value in array
    }
 
    int k = max - min + 1; // Size of count array
 
    int count_array[k]; // Create a count_array to store count of each individual input value
    fill_n(count_array, k, 0); // Initialize count_array elements as zero
 
    for(int i = 0; i < n; i++)
        count_array[input[i] - min]++; // Store count of each individual input value
 
    /* Change count_array so that count_array now contains actual
     position of input values in output array */
    for(int i = 1; i < k; i++)
        count_array[i] += count_array[i - 1];
 
 
    // Populate output array using count_array and input array
    for(int i = 0; i < n; i++)
    {
        output[count_array[input[i] - min] - 1] = input[i];
        count_array[input[i] - min]--;
    }
 
 
    for(int i = 0; i < n; i++)
        input[i] = output[i]; // Copy the output array to input, so that input now contains sorted values
 
}
 
 
// Driver program to test above function
int main()
{
    int n = 9, i;
 
    int input[] = {1, 5, 2, 7, 3, 4, 4, 1, 5};
 
    counting_sort(input, n);
 
    cout << "Sorted Array : ";
    for(i = 0; i < n; i++)
        cout << input[i] << "  ";
 
    return 0;
}
 
 
/* Output
Sorted Array : 1  1  2  3  4  4  5  5  7
*/

Code Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
def counting_sort(input):
    output = [0] * len(input)
    max = input[0]
    min = input[0]
 
    for i in range(1, len(input)):
        if input[i] > max:
            max = input[i]
        elif input[i] < min:
            min = input[i]
 
    k = max - min + 1
 
    count_list = [0] * k
 
    for i in range(0, len(input)):
        count_list[input[i] - min] += 1
 
    for i in range(1, k):
        count_list[i] += count_list[i - 1]
 
    for i in range(0, len(input)):
        output[count_list[input[i] - min] - 1] = input[i]
        count_list[input[i] - min] -= 1
 
    for i in range(0, len(input)):
        input[i] = output[i]
 
 
input = [1, 5, 2, 7, 3, 4, 4, 1, 5]
 
counting_sort(input)
 
print("Sorted list :", end = " ")
for i in range(0, len(input)):
    print(input[i], end = " ")
 
 
''' Output
Sorted list : 1  1  2  3  4  4  5  5  7
'''

Các source code cài đặt trên đây được tham khảo tại Github.