Chương trình C cho thuật toán Radix Sort

Thuật toán sắp xếp (sorting algorithm) sắp xếp các phần tử theo thứ tự nhất định (thường là số hoặc từ điển).

Radix Sort là thuật toán sắp xếp không so sánh (non-comparative). Ưu tiên cho danh sách chưa sắp xếp. Sắp xếp theo từng chữ số từ chữ số ít quan trọng nhất (LSD) đến chữ số quan trọng nhất (MSD).

Ý tưởng: nhóm các chữ số cùng vị trí giá trị. Ví dụ: sắp xếp tên theo chữ cái đầu, chia 26 nhóm.

Số vòng lặp phụ thuộc vào số chữ số của số lớn nhất.

Độ phức tạp: O(m·n) với m là số chữ số, n là số phần tử. Vì m thường nhỏ so với n, coi như O(n) tuyến tính.

Thuật toán

Radix_sort(list, n):
  shift = 1
  for loop = 1 đến keysize:
    for entry = 1 đến n:
      bucketnumber = (list[entry].key / shift) % 10
      append bucket[bucketnumber] với list[entry]
    list = combinebuckets()
    shift *= 10

Ví dụ mã nguồn

#include <stdio.h>

int get_max(int a[], int n) {
    int max = a[0];
    for (int i = 1; i < n; i++)
        if (a[i] > max) max = a[i];
    return max;
}

void radix_sort(int a[], int n) {
    int bucket[10][10], bucket_cnt[10];
    int i, j, k, r, NOP = 0, divisor = 1, lar, pass;

    lar = get_max(a, n);
    while (lar > 0) {
        NOP++;
        lar /= 10;
    }

    for (pass = 0; pass < NOP; pass++) {
        for (i = 0; i < 10; i++)
            bucket_cnt[i] = 0;

        for (i = 0; i < n; i++) {
            r = (a[i] / divisor) % 10;
            bucket[r][bucket_cnt[r]] = a[i];
            bucket_cnt[r]++;
        }

        i = 0;
        for (k = 0; k < 10; k++) {
            for (j = 0; j < bucket_cnt[k]; j++) {
                a[i] = bucket[k][j];
                i++;
            }
        }
        divisor *= 10;
        printf("Sau pass %d: ", pass + 1);
        for (i = 0; i < n; i++)
            printf("%d ", a[i]);
        printf("\n");
    }
}

int main() {
    int i, n, a[10];
    printf("Nhap so phan tu can sap xep: ");
    scanf("%d", &n);
    printf("Nhap cac phan tu: ");
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);

    radix_sort(a, n);

    printf("Mang da sap xep: ");
    for (i = 0; i < n; i++)
        printf("%d ", a[i]);
    printf("\n");
    return 0;
}

Kết quả đầu ra

Nhap so phan tu: 6
Nhap cac phan tu: 567 789 121 212 563 562
Sau pass 1: 121 212 562 563 567 789
Sau pass 2: 212 121 562 563 567 789
Sau pass 3: 121 212 562 563 567 789
Mang da sap xep: 121 212 562 563 567 789