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.
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.
