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

อัลกอริทึมการจัดเรียง เป็นอัลกอริธึมที่จัดองค์ประกอบของรายชื่อในลำดับที่แน่นอน คำสั่งที่ใช้มากที่สุดคือลำดับตัวเลขและลำดับพจนานุกรม

รัศมี sort คืออัลกอริธึมการเรียงลำดับแบบไม่เปรียบเทียบ อัลกอริทึมการเรียงลำดับ Radix เป็นอัลกอริธึมที่ต้องการมากที่สุดสำหรับรายการที่ไม่เรียงลำดับ

โดยจะจัดเรียงองค์ประกอบโดยเริ่มจัดกลุ่มตัวเลขแต่ละรายการของค่าสถานที่เดียวกัน แนวคิดของ Radix Sort คือการทำ digit โดย digit sort เริ่มต้นจาก digit ที่มีนัยสำคัญน้อยที่สุด (LSD) ไปจนถึง digit ที่มีนัยสำคัญที่สุด (MSD) ตามลำดับการเพิ่มขึ้น/ลดลง การเรียงลำดับ Radix เป็นวิธีการเล็กๆ ที่ใช้หลายครั้งเมื่อเรียงตามตัวอักษรสำหรับรายชื่อขนาดใหญ่ โดยเฉพาะอย่างยิ่ง รายชื่อจะถูกจัดเรียงตามอักษรตัวแรกของทุกชื่อ กล่าวคือ ชื่อจะถูกจัดเรียงเป็น 26 หมวดหมู่

ให้เราตรวจสอบภาพประกอบต่อไปนี้เพื่อทำความเข้าใจอย่างชัดเจนเกี่ยวกับการทำงานของอัลกอริธึมการเรียงลำดับ Radix เห็นได้ชัดว่าจำนวนการผ่าน/วนซ้ำขึ้นอยู่กับขนาดของจำนวนบุคคลสูงสุด

ในตัวอย่างข้างต้น คอลัมน์หลักคืออินพุต คอลัมน์ที่เหลือจะแสดงรายการหลังจากเรียงลำดับตามตำแหน่งตัวเลขที่มีนัยสำคัญมากขึ้นเรื่อยๆ

การวิเคราะห์ความซับซ้อนของ Radix Sort O(m.n)

อย่างไรก็ตาม หากเราดูที่ค่า 2 ค่านี้ ขนาดของคีย์จะค่อนข้างเล็กเมื่อเทียบกับจำนวนคีย์ ตัวอย่างเช่น ถ้าเรามีคีย์หกหลัก เราอาจมีระเบียนที่แตกต่างกัน 1,000,000 รายการ

ในที่นี้ เรามักจะเห็นว่าขนาดของคีย์ไม่สำคัญ และอัลกอริธึมนี้มีคุณภาพเชิงเส้น O(n)

อัลกอริทึม

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

ตัวอย่าง

นี่คือโปรแกรม C ที่ใช้ Radix Sort

#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