Chương trình C++ triển khai thuật toán Counting Sort (Sắp xếp đếm)

Counting Sort (Sắp xếp đếm) là một kỹ thuật sắp xếp ổn định (stable), dùng để sắp xếp các đối tượng theo các khóa là các số nhỏ. Nó đếm số lượng khóa có giá trị khóa giống nhau. Kỹ thuật sắp xếp này hiệu quả khi sự khác biệt giữa các khóa không quá lớn, ngược lại nó có thể tăng độ phức tạp không gian.

Độ phức tạp của kỹ thuật Counting Sort

• Độ phức tạp thời gian: O(n + r)
• Độ phức tạp không gian: O(n + r)

Đầu vào — Danh sách dữ liệu chưa sắp xếp: 2 5 6 2 3 10 3 6 7 8

Đầu ra — Mảng sau khi sắp xếp: 2 2 3 3 5 6 6 7 8 10

Thuật toán

countingSort(array, size)

Đầu vào: Mảng dữ liệu, và tổng số phần tử trong mảng

Đầu ra: Mảng đã sắp xếp

Bắt đầu
    max = lấy phần tử lớn nhất từ mảng.
    Định nghĩa mảng count kích thước [max+1]
    for i := 0 đến max
        count[i] = 0 // đặt tất cả phần tử trong mảng count về 0
    for i := 1 đến size
        Tăng count của mỗi số tìm thấy trong mảng
    for i := 1 đến max
        count[i] = count[i] + count[i-1] // tìm tần suất tích lũy
    for i := size xuống 1
        Lưu số vào mảng đầu ra
        Giảm count[i]
    Trả về mảng đầu ra
Kết thúc

Mã ví dụ

#include <iostream>
#include <algorithm>
using namespace std;

void display(int *array, int size) {
    for(int i = 1; i <= size; i++)
        cout << array[i] << " ";
    cout << endl;
}

int getMax(int array[], int size) {
    int max = array[1];
    for(int i = 2; i <= size; i++) {
        if(array[i] > max)
            max = array[i];
    }
    return max;
}

void countSort(int *array, int size) {
    int output[size+1];
    int max = getMax(array, size);
    int count[max+1];
    for(int i = 0; i <= max; i++)
        count[i] = 0;
    for(int i = 1; i <= size; i++)
        count[array[i]]++;
    for(int i = 1; i <= max; i++)
        count[i] += count[i-1];
    for(int i = size; i >= 1; i--) {
        output[count[array[i]]] = array[i];
        count[array[i]] -= 1;
    }
    for(int i = 1; i <= size; i++) {
        array[i] = output[i];
    }
}

int main() {
    int n;
    cout << "Nhập số lượng phần tử: ";
    cin >> n;
    int arr[n+1];
    cout << "Nhập các phần tử:" << endl;
    for(int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    cout << "Mảng trước khi sắp xếp: ";
    display(arr, n);
    countSort(arr, n);
    cout << "Mảng sau khi sắp xếp: ";
    display(arr, n);
}

Kết quả đầu ra

Nhập số lượng phần tử: 10
Nhập các phần tử: 2 5 6 2 3 10 3 6 7 8
Mảng trước khi sắp xếp: 2 5 6 2 3 10 3 6 7 8
Mảng sau khi sắp xếp: 2 2 3 3 5 6 6 7 8 10