Counting Sort là một thuật toán sắp xếp dựa trên đếm số lần xuất hiện của mỗi phần tử trong mảng cần sắp xếp. Nó là một thuật toán sắp xếp linh hoạt và nhanh chóng cho các mảng có giá trị nhỏ và có số lần xuất hiện cụ thể.
Counting Sort sử dụng một mảng đếm để lưu trữ số lần xuất hiện của mỗi phần tử trong mảng cần sắp xếp. Sau đó, nó sử dụng mảng đếm để tính vị trí mới của mỗi phần tử trong mảng đã sắp xếp.
Độ phức tạp thời gian của Counting Sort là O(n+k) với n là số phần tử trong mảng cần sắp xếp và k là giá trị lớn nhất của mỗi phần tử.
Các bài viết liên quan:
Ưu điểm của Counting Sort
- Độ phức tạp thời gian thấp: Counting Sort là một thuật toán sắp xếp đột xuất với độ phức tạp thời gian là O(n + k), trong đó n là số phần tử trong mảng cần sắp xếp và k là giá trị lớn nhất của mỗi phần tử.
- Sắp xếp bất kỳ loại dữ liệu: Counting Sort có thể sắp xếp bất kỳ loại dữ liệu nào có giá trị nhỏ và có số lần xuất hiện cụ thể.
- Không tùy chọn: Counting Sort không yêu cầu bất kỳ thuật toán sắp xếp nào để hoạt động, vì vậy nó là một thuật toán rất dễ sử dụng.
- Không yêu cầu bộ nhớ phụ: Counting Sort chỉ yêu cầu một mảng đếm và một mảng kết quả, vì vậy nó không yêu cầu bộ nhớ phụ bất kỳ loại nào.
- Stable sort: Counting Sort là một thuật toán sắp xếp ổn định, nghĩa là nó giữ nguyên thứ tự giữa các phần tử có giá trị giống nhau.
Ví dụ về Counting Sort trong c++
#include <iostream> using namespace std; // Hàm Counting Sort void countingSort(int arr[], int n) { int output[n]; // Mảng kết quả int count[10] = {0}; // Tính số lần xuất hiện của mỗi phần tử for (int i = 0; i < n; i++) count[arr[i]]++; // Chuyển count[] sang bảng đếm tích lũy for (int i = 1; i <= 9; i++) count[i] += count[i - 1]; // Xây dựng mảng kết quả for (int i = n - 1; i >= 0; i--) { output[count[arr[i]] - 1] = arr[i]; count[arr[i]]--; } // Sao chép mảng kết quả vào mảng ban đầu for (int i = 0; i < n; i++) arr[i] = output[i]; } int main() { int arr[] = {1, 4, 1, 2, 7, 5, 2}; int n = sizeof(arr) / sizeof(arr[0]); cout << "Mảng trước khi sắp xếp: "; for (int i = 0; i < n; i++) cout << arr[i] << " "; countingSort(arr, n); cout << "\nMảng sau khi sắp xếp: "; for (int i = 0; i < n; i++) cout << arr[i] << " "; return 0; }
Đoạn code trên là ví dụ về thuật toán Counting Sort trong C++.
- Dòng 6: Khai báo mảng
output
để lưu kết quả sau khi sắp xếp. - Dòng 7: Khai báo mảng
count
với giá trị ban đầu là 0 để lưu số lần xuất hiện của mỗi phần tử. - Dòng 10: Duyệt qua mảng
arr
và tính số lần xuất hiện của mỗi phần tử bằng cách tăng giá trị tại vị trí tương ứng trong mảngcount
. - Dòng 13: Duyệt qua mảng
count
và chuyển giá trị thành bảng đếm tích lũy bằng cách cộng giá trị tại vị trí hiện tại với giá trị tại vị trí trước đó. - Dòng 16: Duyệt qua mảng
arr
từ cuối mảng đến đầu mảng và xây dựng mảng kết quảoutput
. Tại mỗi vị trí, giá trị tại vị trícount[arr[i]] - 1
trong mảngoutput
sẽ bằngarr[i]
và giá trị tại vị trícount[arr[i]]
trong mảngcount
sẽ giảm đi 1. - Dòng 22: Duyệt qua mảng
output
và sao chép giá trị vào mảngarr
. - Dòng 25: In mảng trước khi sắp xếp.
- Dòng 28: Gọi hàm
countingSort
để sắp xếp mảng