Rate this post

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:

Tóm tắt nội dung

Khái niệm về Counting Sort

Counting Sort là một thuật toán sắp xếp đơn giản và hiệu quả, được sử dụng để sắp xếp một dãy các phần tử có giá trị nguyên từ một khoảng giá trị cụ thể. Thuật toán này hoạt động dựa trên việc đếm số lần xuất hiện của mỗi giá trị trong dãy đầu vào để xác định vị trí đúng của từng phần tử trong dãy kết quả.

Counting Sort hoạt động hiệu quả khi các giá trị trong dãy đầu vào không quá lớn và chênh lệch giữa các giá trị không quá xa nhau. Thuật toán này không sử dụng phép so sánh trực tiếp giữa các phần tử, do đó có độ phức tạp thời gian tuyến tính O(n+k), trong đó n là số phần tử trong dãy đầu vào và k là khoảng giá trị của các phần tử.

Quá trình hoạt động của Counting Sort bao gồm các bước sau:

Xác định khoảng giá trị của các phần tử trong dãy đầu vào.
Tạo một mảng đếm (counting array) có kích thước bằng khoảng giá trị và khởi tạo ban đầu các phần tử là 0.
Đếm số lần xuất hiện của từng giá trị trong dãy đầu vào và lưu trữ vào mảng đếm.
Tính tổng các phần tử trong mảng đếm để xác định vị trí đúng của từng giá trị trong dãy kết quả.
Tạo một mảng kết quả có kích thước bằng số phần tử trong dãy đầu vào.
Đặt từng phần tử vào vị trí đúng trong dãy kết quả dựa trên thông tin từ mảng đếm.
Counting Sort là một thuật toán đơn giản và nhanh chóng khi áp dụng cho các tình huống phù hợp. Tuy nhiên, nó chỉ áp dụng được cho các dãy số nguyên và yêu cầu bộ nhớ phụ có kích thước tương đối lớn tùy thuộc vào khoảng giá trị của các phần tử.

Cách thức hoạt động của Counting Sort

Counting Sort hoạt động theo các bước sau:

Xác định khoảng giá trị: Đầu tiên, chúng ta cần xác định khoảng giá trị của các phần tử trong dãy đầu vào. Điều này cho phép chúng ta tạo một mảng đếm (counting array) có kích thước tương ứng với khoảng giá trị và khởi tạo ban đầu các phần tử là 0.
Đếm số lần xuất hiện: Tiếp theo, chúng ta lần lượt duyệt qua dãy đầu vào và đếm số lần xuất hiện của từng giá trị. Khi gặp một giá trị, chúng ta tăng giá trị tương ứng trong mảng đếm lên 1.
Tính tổng các phần tử: Sau khi đã đếm số lần xuất hiện của từng giá trị, chúng ta tính tổng các phần tử trong mảng đếm. Quá trình này giúp chúng ta biết được vị trí đúng của từng giá trị trong dãy kết quả.
Xác định vị trí đúng: Tiếp theo, chúng ta tạo một mảng kết quả có kích thước bằng số phần tử trong dãy đầu vào. Chúng ta duyệt qua dãy đầu vào lần nữa và đặt từng phần tử vào vị trí đúng trong dãy kết quả dựa trên thông tin từ mảng đếm.
Hoàn thành quá trình sắp xếp: Khi đã đặt từng phần tử vào vị trí đúng trong dãy kết quả, quá trình sắp xếp bằng Counting Sort hoàn thành.

Counting Sort hoạt động dựa trên việc đếm số lần xuất hiện của các giá trị để xác định vị trí đúng của từng phần tử trong dãy kết quả. Điều này làm cho thuật toán có độ phức tạp thời gian tuyến tính O(n+k), trong đó n là số phần tử trong dãy đầu vào và k là khoảng giá trị của các phần tử.

Một điểm quan trọng cần lưu ý là Counting Sort chỉ áp dụng được cho các dãy số nguyên và yêu cầu bộ nhớ phụ có kích thước tương đối lớn tùy thuộc vào khoảng giá trị của các phần tử.

Độ phức tạp thời gian và không gian của Counting Sort

Độ phức tạp thời gian và không gian của Counting Sort là như sau:

Độ phức tạp thời gian: Trong trường hợp tốt nhất, trung bình và xấu nhất, độ phức tạp thời gian của Counting Sort là O(n+k), trong đó n là số lượng phần tử trong dãy đầu vào và k là khoảng giá trị của các phần tử. Điều này có nghĩa là thuật toán chạy với tốc độ tuyến tính và không phụ thuộc vào kích thước của dữ liệu đầu vào.
Độ phức tạp không gian: Counting Sort yêu cầu một mảng đếm (counting array) có kích thước bằng khoảng giá trị của các phần tử trong dãy đầu vào. Do đó, độ phức tạp không gian của Counting Sort là O(k), với k là khoảng giá trị của các phần tử. Điều này có nghĩa là không gian cần thiết để thực hiện thuật toán tương đối lớn, đặc biệt khi khoảng giá trị của các phần tử lớn.

Điểm quan trọng cần lưu ý là độ phức tạp thời gian tốt của Counting Sort chỉ đạt được khi khoảng giá trị của các phần tử không quá lớn và chênh lệch giữa các giá trị không quá xa nhau. Nếu khoảng giá trị rất lớn, hoặc chênh lệch giữa các giá trị quá xa nhau, thì Counting Sort có thể trở nên không hiệu quả vì yêu cầu bộ nhớ phụ lớn và không đáp ứng được độ phức tạp không gian O(k).

Tuy nhiên, Counting Sort vẫn là một thuật toán rất hữu ích trong các tình huống mà các điều kiện trên được đáp ứng, và nó được ưu tiên sử dụng khi các giá trị không quá lớn và gần nhau.

Xem thêm bubble sort trong c++

So sánh Counting Sort với các thuật toán sắp xếp khác

So sánh Counting Sort với các thuật toán sắp xếp khác, chẳng hạn như Bubble Sort, Insertion Sort và Quick Sort, có thể được thực hiện dựa trên các yếu tố như độ phức tạp thời gian, độ phức tạp không gian và khả năng xử lý các loại dữ liệu khác nhau. Dưới đây là một so sánh giữa Counting Sort và các thuật toán sắp xếp khác:

Bubble Sort:

Độ phức tạp thời gian: O(n^2) trong trường hợp tốt nhất, trung bình và xấu nhất.
Độ phức tạp không gian: O(1) vì không cần bộ nhớ phụ.
Bubble Sort là thuật toán đơn giản nhưng không hiệu quả cho các tập dữ liệu lớn. Nó thường được sử dụng cho các tập dữ liệu nhỏ hoặc đã gần được sắp xếp.

Insertion Sort:

Độ phức tạp thời gian: O(n^2) trong trường hợp tốt nhất, trung bình và xấu nhất.
Độ phức tạp không gian: O(1) vì không cần bộ nhớ phụ.
Insertion Sort hiệu quả cho các tập dữ liệu nhỏ hoặc gần được sắp xếp, nhưng không hiệu quả cho các tập dữ liệu lớn.

Quick Sort:

Độ phức tạp thời gian: O(nlog(n)) trong trường hợp tốt nhất và trung bình, O(n^2) trong trường hợp xấu nhất.
Độ phức tạp không gian: O(log(n)) trong trường hợp tốt nhất và trung bình, O(n) trong trường hợp xấu nhất.
Quick Sort là một thuật toán sắp xếp nhanh và hiệu quả cho các tập dữ liệu lớn. Tuy nhiên, độ phức tạp trong trường hợp xấu nhất có thể xảy ra khi dữ liệu đã gần được sắp xếp.

Counting Sort:

Độ phức tạp thời gian: O(n+k) trong trường hợp tốt nhất, trung bình và xấu nhất.
Độ phức tạp không gian: O(k).
Counting Sort hiệu quả cho các tập dữ liệu với khoảng giá trị nhỏ và chênh lệch giữa các giá trị không quá xa nhau. Nó không sử dụng phép so sánh trực tiếp giữa các phần tử, do đó có thể nhanh hơn các thuật toán sử dụng phép so sánh.

Tổng quan, Counting Sort có thể là lựa chọn tốt khi dữ liệu có khoảng giá trị nhỏ và chênh lệch nhỏ giữa các giá trị. Nếu dữ liệu không đáp ứng các yêu cầu này, các thuật toán sắp xếp khác như Quick Sort, Merge Sort hay Heap Sort có thể là những lựa chọn tốt hơn.

Xem thêm Gnome Sort là gì ?

Ư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ảng count.
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ảng output sẽ bằng arr[i] và giá trị tại vị trí count[arr[i]] trong mảng count sẽ giảm đi 1.
Dòng 22: Duyệt qua mảng output và sao chép giá trị vào mảng arr.
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

Xem thêm Thuật toán Shell Sort là gì ?

Algorithm, C/C++

Counting Sort là gì ?