โปรแกรม C สำหรับ Radix Sort

Sorting Algorithm คืออัลกอริทึมจัดเรียงสมาชิกในลิสต์ เรียงลำดับตัวเลขหรือตัวอักษร

Radix Sort เป็น non-comparative sorting algorithm (ไม่เปรียบเทียบระหว่างสมาชิกโดยตรง) เป็นอัลกอริทึมที่นิยมสำหรับลิสต์ที่ไม่ได้จัดเรียง

จัดกลุ่มตัวเลขตามตำแหน่งหลัก (digit) เริ่มจากหลักหน่วย (LSD) ไปหาหลักสำคัญที่สุด (MSD) ตามลำดับเพิ่ม/ลด ใช้หลายรอบเมื่อจัดเรียงชื่อจำนวนมาก เริ่มจากตัวอักษรแรกของชื่อ จัดเป็น 26 กลุ่ม

จำนวนรอบ (pass) ขึ้นอยู่กับขนาดตัวเลขที่ใหญ่ที่สุด

Complexity: O(m·n) โดย m = จำนวนหลักสูงสุด n = จำนวนสมาชิก แต่เนื่องจาก m เล็กกว่า n มาก จึงถือเป็น O(n) แบบเส้นตรง

อัลกอริทึม

Radix_sort(list, n):
    shift = 1
    for loop = 1 to keysize:
        for entry = 1 to n:
            bucketnumber = (list[entry].key / shift) mod 10
            append(bucket[bucketnumber], list[entry])
        list = combinebuckets()
        shift = shift * 10

ตัวอย่างโค้ด

#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] += 1;
        }
        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("After pass %d : ", pass + 1);
        for (i = 0; i < n; i++) printf("%d ", a[i]);
        printf("\n");
    }
}

int main() {
    int i, n, a[10];
    printf("Enter the number of items to be sorted: ");
    scanf("%d", &n);
    printf("Enter items: ");
    for (i = 0; i < n; i++) scanf("%d", &a[i]);
    radix_sort(a, n);
    printf("Sorted items : ");
    for (i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

เอาต์พุต

Enter number of items to be sorted
6
Enter items: 567 789 121 212 563 562
After pass 1 : 121 212 562 563 567 789
After pass 2 : 212 121 562 563 567 789
After pass 3 : 121 212 562 563 567 789
Sorted items : 121 212 562 563 567 789