โปรแกรม C++ อัลกอริทึม Radix Sort

Radix Sort

Radix sort เป็นอัลกอริทึมการจัดเรียงที่ไม่ใช่แบบเปรียบเทียบ (non-comparative sorting algorithm) อัลกอริทึมนี้ทำงานบนกุญแจจำนวนเต็ม (integer keys) โดยจัดกลุ่มหลัก (digits) ที่มีตำแหน่งและค่าเท่ากัน Radix คือฐาน (base) ของระบบตัวเลข ตามที่เรารู้ในระบบทศนิยม radix หรือฐานคือ 10 ดังนั้นสำหรับการจัดเรียงตัวเลขทศนิยมบางตัว เราต้องการกล่องตำแหน่ง 10 กล่องเพื่อเก็บตัวเลข

ความซับซ้อนของ Radix Sort

• Time Complexity: O(nk)

• Space Complexity: O(n+k)

Input - รายการที่ไม่ได้จัดเรียง: 802 630 20 745 52 300 612 932 78 187
Output - Data after Sorting: 20 52 78 187 300 612 630 745 802 932

อัลกอริทึม

radixSort(array, size, maxDigit)

Input: อาร์เรย์ข้อมูล, จำนวนรวมในอาร์เรย์, จำนวนหลักของตัวเลขสูงสุด

Output: อาร์เรย์ที่จัดเรียงแล้ว

เริ่มต้น
  ประกาศ 10 รายการเป็น pocket
  for i := 0 ถึง max-1
    m = 10^(i+1)
    p = 10^i
    for j := 0 ถึง n-1
      temp := array[j] mod m
      index := temp / p
      pocket[index].append(array[j])
  count := 0
  for j := 0 ถึง radix
    while pocket[j] ไม่ว่าง
      array[count] := ดึงโหนดแรกของ pocket[j] และลบมัน
      count := count + 1
สิ้นสุด

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

#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 << "Enter the number of elements: ";
    cin >> n;
    cout << "Enter the maximum digit of elements: ";
    cin >> max;
    int arr[n];
    cout << "Enter elements:" << endl;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << "Data before Sorting: ";
    display(arr, n);
    radixSort(arr, n, max);
    cout << "Data after Sorting: ";
    display(arr, n);
}

ผลลัพธ์ตัวอย่าง

Enter the number of elements: 10
Enter the maximum digit of elements: 3
Enter elements: 802 630 20 745 52 300 612 932 78 187
Data before Sorting: 802 630 20 745 52 300 612 932 78 187
Data after Sorting: 20 52 78 187 300 612 630 745 802 932