Thuật toán Radix Sort (Sắp xếp cơ số)

Radix Sort là thuật toán sắp xếp không so sánh (non-comparative). Sắp xếp các khóa nguyên bằng cách nhóm các chữ số cùng vị trí và giá trị. Cơ số (radix) là cơ số của hệ thống đếm. Hệ thập phân cơ số 10 → cần 10 hộp (bucket) để chứa số.

Độ phức tạp Radix Sort

• Time Complexity: O(nk) (k = số chữ số lớn nhất)
• Space Complexity: O(n + k)

Input và Output

Input: Danh sách chưa sắp xếp: 802 630 20 745 52 300 612 932 78 187
Output: Dữ liệu trước: 802 630 20 745 52 300 612 932 78 187
Dữ liệu sau: 20 52 78 187 300 612 630 745 802 932

Thuật toán

radixSort(array, size, maxDigit)
Input: Mảng dữ liệu, số phần tử, số chữ số của max
Output: Mảng đã sắp xếp

Begin
  định nghĩa 10 list làm pocket (bucket)
  for i := 0 to max-1 do
    m = 10^(i+1), p = 10^i
    for j := 0 to n-1 do
      temp = array[j] % m
      index = temp / p
      pocket[index].append(array[j])
    done
    count := 0
    for j := 0 to 9 do
      while pocket[j] không rỗng do
        array[count] := lấy node đầu pocket[j] và xóa
        count++
      done
    done
  done
End

Ví dụ (C++)

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

void display(int *a, int n) { for(int i=0;i> n;
    cout << "Số chữ số max: "; cin >> maxD;
    int arr[n];
    for(int i=0;i> arr[i];
    cout << "Trước: "; display(arr,n);
    radixSort(arr, n, maxD);
    cout << "Sau: "; display(arr,n);
}

Kết quả

Số phần tử: 10
Số chữ số max: 3
Nhập phần tử: 802 630 20 745 52 300 612 932 78 187
Trước: 802 630 20 745 52 300 612 932 78 187
Sau: 20 52 78 187 300 612 630 745 802 932

Đặc điểm: Radix Sort ổn định, không so sánh, xử lý từng chữ số từ LSD (least significant digit) đến MSD. Hiệu quả cho số nguyên, chuỗi ký tự cùng độ dài. Cần biết trước maxDigit.