Radix Sort

Radix Sort

     Radix sort เป็นการจัดเรียงแบบกระจายอีกแบบหนึ่งที่ใช้เทคนิคของ Bucket sort มาประยุกต์เพื่อให้เกิดประสิทธิภาพในการจัดเรียงที่ดีกว่า ในการจัดเรียงแบบ Radix sort นี้เราจะใช้จานวนสูงสุดของตัวเลข (digit) ที่มีอยู่ใน int (สมมติว่าข้อมูลที่ต้องการจัดเรียงเป็น int) เป็นตัวกาหนดจานวนครั้งของการกระจาย เราจะจัดเรียง digit ทีละรอบโดยเริ่มต้นจาก digit ทางด้านขวาสุด (least significant digit) จนกระทั่งเราไม่มี digit ใด ๆ เหลืออยู่ในตัวเลขนั้น  แสดงขั้นตอนการจัดเรียงด้วยการใช้ Radix sort algorithm (ตัวเลขที่เป็นตัวหนาแสดงถึง radix ที่ใช้เป็นตัวกาหนดการจัดเรียง)


     ในการเขียน code รองรับการทางานของ Radix sort นั้น เราเลือกใช้ LinkedList เป็นตัวเก็บข้อมูลตาม radix (หรือตาแหน่งของ digit ในตัวเลข) ที่หาได้โดยเราจะเก็บจาก digit ที่อยู่ทางขวาสุดก่อนเป็นอันดับแรก และจะเลื่อนไปทางซ้ายจนกว่าจะหมดจานวนของ digit ที่มีอยู่ และก่อนที่เราจะไปดูกันถึง code ของ Radix sort เรามาดูคาสั่งในการหา radix ก่อน

//return radix of a numver e.g.
//first radix of 3476 is 6, second is 7 etc.
private int getRadix(int number, int radix) {
     return (int)(number / Math.pow(10, radix - 1)) % 10;
}

    การหา radix ก็ไม่ยาก เราเพียงแค่หารตัวเลขที่เราต้องการหา radix ด้วย 10 ยกกาลังตาแหน่งของ digit ที่เราต้องการหาลบหนึ่ง เช่น ถ้าเราต้องการหา radix ที่ 2 ของ 3476 เราก็หาร 3476 ด้วย 10(2-1) ได้ผลลัพธ์เท่าไร เราก็หาเศษจากผลลัพธ์นี้ด้วยการนาสิบไปหาร (mod) เพราะฉะนั้นเราก็จะได้ radix เป็น (3476 / 101) % 10 = 347 % 10 = 7 เราก็จะเก็บข้อมูลทุกตัวที่มี radix เท่ากับ 7 ไว้ใน array list[7]เมื่อเราได้ radix ที่ว่าแล้วเราก็ใช้ radix ตัวนี้เป็นตัวกาหนด (key) ในการจัดเรียงเหมือนกับที่เราทาใน Bucket sort ส่วนของ code ที่เห็นนี้มี list เป็น LinkedList ที่เราใช้เก็บข้อมูลตาม radix ที่เราได้มา โดยเราจะใช้การนาเข้าด้านหลังของ LinkedList เป็นหลัก

for(int j = 0; j < arr.length; j++) {
     list[getRadix(arr[j], i)].add(arr[j]);
}

     หลังจากที่เราได้ข้อมูลใน LinkedList ซึ่งเป็นข้อมูลที่ถูกจัดเก็บตามค่าของ radix เราก็จะดึงเอาข้อมูลเหล่านี้ออกจาก LinkedList ซึ่งการนาออกนั้น เราจะใช้การนาออกทางด้านหน้าเป็นหลัก (ผู้อ่านอาจสงสัยว่าทาไมเราไม่ใช้ Queue ในการจัดเก็บนี้ คาตอบก็คือ เราสามารถทาได้แต่ Java ก็มีวิธีการนาเข้าและดึงออกในรูปแบบที่คล้ายกันกับการทางานของ Queue จาก class LinkedList ดังนั้นเราจึงเรียกใช้ LinkedList ของ Java แทน Queue)

เราจะนาข้อมูลที่เราดึงออกมาจาก LinkedList กลับเข้าสู่ array ใหม่เพื่อการจัดเรียงในรอบต่อไป ดัง code ที่เห็นนี้

for(int j = 0; j < list.length; j++) {
     while(!list[j].isEmpty()) {
           arr[index] = (Integer)list[j].removeFirst();
                index++;
      }
}

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

int max = 0;
for(int i = 0; i < arr.length; i++) {
      max = Math.max(max, arr[i]);
}
int digits = (int)(Math.log10((double)max)) + 1;

ก่อนอื่นเราต้องหาค่าสูงสุดที่มีอยู่ในกลุ่มเสียก่อน ซึ่งเราก็ทาง่าย ๆ ใน for i/loop ที่เห็น และเมื่อเราได้ค่าสูงสุดแล้ว เราก็หาจานวนของ digit ที่มีอยู่ในค่าที่ว่านี้ด้วยคาสั่ง

int digits = (int)(Math.log10((double)max)) + 1;

อย่างไรก็ตาม ถ้าจะให้ได้จานวนของ digit ในตัวเลขที่ไม่ต้องมีการคานวณจากฟังก์ชั่นทางคณิตศาสตร์ เราก็สามารถทาได้ด้วยการใช้ loop หาจานวนที่ว่านี้แทน

ไม่มีความคิดเห็น:

แสดงความคิดเห็น

สมัครสมาชิก: บทความ (Atom)