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:

Ư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

Algorithm, C/C++

Counting Sort là gì

Ưu điểm của Counting Sort

Ví dụ về Counting Sort trong c++

Trả lời Hủy