DAA - เรียง Radix

Radix sortเป็นวิธีการเล็ก ๆ ที่หลายคนใช้โดยสังหรณ์ใจเมื่อเรียงตามตัวอักษรของรายชื่อจำนวนมาก โดยเฉพาะอย่างยิ่งรายชื่อจะถูกเรียงลำดับตามตัวอักษรตัวแรกของแต่ละชื่อนั่นคือรายชื่อจะถูกจัดเรียงใน 26 คลาส

โดยสัญชาตญาณเราอาจต้องการจัดเรียงตัวเลขตามหลักที่สำคัญที่สุดของตน อย่างไรก็ตามการเรียงลำดับ Radix จะตอบโต้โดยสังหรณ์ใจโดยการเรียงลำดับตัวเลขที่มีนัยสำคัญน้อยที่สุดก่อน ในรอบแรกตัวเลขทั้งหมดจะเรียงตามหลักที่มีนัยสำคัญน้อยที่สุดและรวมกันในอาร์เรย์ จากนั้นในรอบที่สองตัวเลขทั้งหมดจะถูกจัดเรียงอีกครั้งบนเลขนัยสำคัญน้อยที่สุดอันดับสองและรวมกันในอาร์เรย์เป็นต้น

Algorithm: 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

การวิเคราะห์

แต่ละคีย์จะถูกมองพร้อมกันสำหรับแต่ละหลัก (หรือตัวอักษรหากคีย์เป็นตัวอักษร) ของคีย์ที่ยาวที่สุด ดังนั้นหากคีย์ที่ยาวที่สุดมีm หลักและมี n คีย์การเรียงลำดับรัศมีมีลำดับ O(m.n).

อย่างไรก็ตามหากเราดูสองค่านี้ขนาดของคีย์จะค่อนข้างเล็กเมื่อเทียบกับจำนวนคีย์ ตัวอย่างเช่นหากเรามีคีย์หกหลักเราอาจมีบันทึกต่างกันเป็นล้านรายการ

ที่นี่เราเห็นว่าขนาดของคีย์ไม่สำคัญและอัลกอริทึมนี้มีความซับซ้อนเชิงเส้น O(n).

ตัวอย่าง

ตัวอย่างต่อไปนี้แสดงให้เห็นว่าการเรียงลำดับ Radix ทำงานบนตัวเลข 3 หลักเจ็ดตัวอย่างไร

อินพุต	1 st Pass	พาสครั้งที่ 2	3 ถผ่าน
329	720	720	329
457	355	329	355
657	436	436	436
839	457	839	457
436	657	355	657
720	329	457	720
355	839	657	839

ในตัวอย่างข้างต้นคอลัมน์แรกคืออินพุต คอลัมน์ที่เหลือจะแสดงรายการหลังจากเรียงลำดับตามตำแหน่งตัวเลขที่มีนัยสำคัญมากขึ้น รหัสสำหรับการเรียง Radix จะถือว่าแต่ละองค์ประกอบในอาร์เรย์A ของ n องค์ประกอบมี d หลักโดยที่หลัก 1 เป็นตัวเลขลำดับต่ำสุดและ d เป็นตัวเลขลำดับสูงสุด