Chương trình C++ triển khai thuật toán Radix Sort (Sắp xếp cơ số)

Radix Sort (Sắp xếp cơ số) là thuật toán sắp xếp không dựa trên so sánh. Thuật toán này hoạt động trên các khóa nguyên bằng cách nhóm các chữ số chia sẻ cùng vị trí và giá trị. Cơ số (radix) là cơ số của một hệ thống số. Như chúng ta biết, trong hệ thập phân, cơ số là 10. Vì vậy, để sắp xếp một số số thập phân, chúng ta cần 10 hộp vị trí để lưu trữ số.

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

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

Đầu vào — Danh sách chưa sắp xếp: 802 630 20 745 52 300 612 932 78 187
Đầu ra — Dữ liệu sau khi sắp xếp: 20 52 78 187 300 612 630 745 802 932

Thuật toán

radixSort(array, size, maxDigit)

Đầu vào: Mảng dữ liệu, tổng số phần tử, số chữ số của số lớn nhất.

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

Bắt đầu
    Định nghĩa 10 danh sách là pocket
    for i := 0 đến max - 1
        m = 10^(i+1)
        p := 10^i
        for j := 0 đến n-1
            temp := array[j] mod m
            index := temp / p
            pocket[index].append(array[j])
    count := 0
    for j := 0 đến radix
        while pocket[j] không rỗng
            array[count] := lấy nút đầu của pocket[j] và xóa nó
            count := count + 1
Kết thúc

Mã ví dụ

#include <iostream>
#include <list>
#include <cmath>
using namespace std;

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

void radixSort(int *arr, int n, int max) {
    int i, j, m, p = 1, index, temp, count = 0;
    list<int> pocket[10];
    for(i = 0; i < max; i++) {
        m = pow(10, i+1);
        p = pow(10, i);
        for(j = 0; j < n; j++) {
            temp = arr[j] % m;
            index = temp / p;
            pocket[index].push_back(arr[j]);
        }
        count = 0;
        for(j = 0; j < 10; j++) {
            while(!pocket[j].empty()) {
                arr[count] = *(pocket[j].begin());
                pocket[j].erase(pocket[j].begin());
                count++;
            }
        }
    }
}

int main() {
    int n, max;
    cout << "Nhập số lượng phần tử: ";
    cin >> n;
    cout << "Nhập số chữ số tối đa của phần tử: ";
    cin >> max;
    int arr[n];
    cout << "Nhập các phần tử:" << endl;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << "Dữ liệu trước khi sắp xếp: ";
    display(arr, n);
    radixSort(arr, n, max);
    cout << "Dữ liệu 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 số chữ số tối đa của phần tử: 3
Nhập các phần tử: 802 630 20 745 52 300 612 932 78 187
Dữ liệu trước khi sắp xếp: 802 630 20 745 52 300 612 932 78 187
Dữ liệu sau khi sắp xếp: 20 52 78 187 300 612 630 745 802 932