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 เป็นตัวเลขลำดับสูงสุด