Google         youtube            psv            สพม.11

การเรียงลำดับแบบเรดิกซ์ 
เป็นแบบสุดท้ายของการเรียงลำดับภายในที่กล่าวถึงและไม่มีการเปรียบเทียบค่า เวลาที่ใช้ทำงานเป็น O(n) มีลักษณะการจัดเรียงลำดับหลายมิติ (Multidimensional Sort) ที่ใช้การเรียงลำดับแบบนับจำนวนในแต่ละประเภทเพื่อกลับลำดับของค่า ซึ่งเป็นการทำงานตามลำดับเพียงครั้งเดียวกับสตริงของเลขดิจิต d ตัว (Digit String) โดยมีการพิจารณาให้แต่ละสตริงเป็นพื้นที่ d มิติ และเรียกว่าการเรียงลำดับแบบเรดิกซ์ ดังในรูปที่ 11.17 สมมุติให้ค่าที่ต้องการจัดเรียงอยู่ในรูปแบบสตริงของเลขดิจิตความยาว d โดยแต่ละตัวในสตริงจะต้องมีค่าอยู่ในช่วง {0,1,2,…,r-1} และ r เป็นค่าคงที่เรียกว่าเรดิกซ์ของสตริง ดังตัวอย่างต่อไปนี้

  1. หมายเลขประจำตัว เช่น 055-36-8161 จะได้ d = 9 และ r = 10(0-9)
  2. หมายเลขรหัสต่างๆ เช่น 1NKSD2659YA035787 จะได้ d = 17 r = 36(0-9, A-Z)
  3. หมายเลขหนังสือ (ISBN) เช่น 3-89028-941-X จะได้ d = 10 r = 11(0-9, X)

รูปที่ 11.17  การเรียงลำดับแบบเรดิกซ์กับสตริงของเลขดิจิตความยาว 8 ตัวจากซ้ายไปขวา

อัลกอริทึมในการจัดเรียงลำดับแบบเรดิกซ์ได้เป็นดังในตารางที่ 11.18

ตารางที่ 11.18  อัลกอริทึมการเรียงลำดับแบบเรดิกซ์

  1. สร้างถัง (Bucket) ตามจำนวนของเลขดิจิตที่ต่างกัน r
  2. ทำขั้นตอนที่ 3-4 สำหรับแต่ละหลักของเลขดิจิตที่ j โดยเริ่มต้นค่าทางด้านขวาสุดก่อนเป็นหลักที่ j = 0
  3. กระจายค่าไปเก็บไว้ในแต่ละถังที่มีเลขดิจิตตรงกัน
  4. คัดลอกค่าทั้งหมดจากทุกถังกลับไปยังอาร์เรย์ตามลำดับเลขดิจิต

การ เรียงลำดับแบบเรดิกซ์จะสร้างถังเท่ากับจำนวน r และกระจายแต่ละค่าเก็บไว้ในถังที่มีเลขดิจิตเท่ากัน หลังจากนั้นนำกลับมารวมกับที่อาร์เรย์ต้นทาง ทำเช่นนี้กับทุกๆ เลขดิจิตตามความยาวของสตริงโดยเริ่มจากเลขดิจิตทางขวาสุดไปยังทางซ้ายสุด ก็ได้ค่าที่เรียงตามลำดับและเวลาที่ใช้ทำงานในกรณีเฉลี่ยเป็น O(n) หรือเส้นตรง เขียนเป็นฟังก์ชันได้เป็นตารางที่ 11.19 มีฟังก์ชันหลัก คือ radixSort และฟังก์ชัน digit ที่ใช้ค่าดัชนีให้กับอาร์เรย์ bucket

int digit( int key, int numDigit ){
int i, exponent = l;

for( i = l; i < numDigit; i++)
exponent += 10;
return (key/exponent) % 10;
}
Void radixSort ( int key[], int size, int numDigit){
Queues bucket[10];

for( i = 0; i < 10; i++)
bucket[10] = createQueue();
for( n = l; n <= numDigit; i++){
for( i = 0; i < size; i++ )
Insert( key[i], bucket[digit(key[i],n)] );
aTemp[ –count[ key[I ] ] ] = key[i];
j = 0;
For( i = 0; i<10; i++)
while(! isEmpty( bucket[i]) )
key[j++] = Remove(bucker[i]);
}
}

ตัวอย่าง การเรียงลำดับแบบเรดิกซ์เมื่อใช้กับค่าในอารเรย์ที่มีสมาชิกเท่ากับ 10 คือ {5132,2810,7853,1069,8316,3195,4062,5377,9421,3507} มีความยาวสตริง d = 4 และ r = 10 ดังนั้น การทำงานของอัลกอริทึมมีทั้งหมด 4 รอบตามความยาวสตริง ดังในรูปที่ 11.18
ในรอบแรกทำการนำตัวเลขที่อยู่ด้านขวาสุด ที่ต่างกันแยกเก็บไว้ในแต่ละถังที่มีเลขดิจิตตรงกัน เช่น ถังที่ 0 เก็บค่า 2810 ถังที่ 2 เก็บค่า 5132 และ 4065 จากนั้นนำกลับมารวมไว้ในอาร์เรย์โดยเรียงตามลำดับเลขดิจิตของถังทำให้มีการ กลับตำแหน่งกันได้ตัวเลขทางขวาสุดเรียงตามลำดับ ในรอบที่สองนำตัวเลขถัดมาทางซ้ายแยกเก็บไว้ในแต่ละถังที่มีเลขดิจิตตรงกัน เช่น ถังที่ 1 เก็บค่า 2810 และ 8316 ถังที่ 3 เก็บค่า 5132 ซึ่งทำแบบเดียวกันในแต่ละรอบกันแต่ละตัวเลขถัดไปทางซ้ายจนครบความยาวสตริงก็ จะได้ค่าที่เรียงตามลำดับ

5132 2810 7853 1069 8316 3195 4062 5377 9421 3507 2810 9421 5132 4062 7853 3195 8316 5377 3507 1069
0

2810

0

3507

1

9421

1

2810

8316

2

5132

2

9421

3

7853

4062

3 5132

4

  —

4

5

3195

5

7853

6

8316

6

4062

1069

7

5377

3507

7

5377

8

  —

8

9

1069

9

3195

5132 2810 7853 1069 8316 3195 4062 5377 9421 3507 2810 9421 5132 4062 7853 3195 8316 5377 3507 1069

รอบที่ 1                                                                                   รอบที่ 2

3507 2810 8316 9421 5132 7853 4062 1069 5377 3195 4062 1069 5132 3195 8316 5377 9421 3507 2810 7853
0

4062

1069

0

1

5132

3195

1

1069

2

2

2810

3 8316

5377

3

3195

3507

4

9421

4

4062

5

3507

5 5132

5377

6

6

7

7

7853

8

2810

7853

8

8316

9

9

9421

4062 1069 5132 3195 8316 5377 9421 3507 2810 7853 1069 2810 3195 3507 4062 5132 5377 7853 8316 9421

รอบที่ 3                                                                                   รอบที่ 4
รูปที่ 11.18  ขั้นตอนการเรียงลำดับแบบเรดิกซ์

                การเลือกลำดับแบบเรดิกซ์จะมีการสร้างถังเพื่อเก็บค่า จึงนำโครงสร้างข้อมูลแบบอื่นมาใช้เป็นถัง ซึ่งอาจเป็นลิ้งค์ลิสต์ในรูปที่ 11.18 หรือใช้เป็นคิวในตารางที่ 11.19  นอกจากจะใช้เลขดิจิตเป็นตัวเลขดังในตัวอย่างแล้ว อาจใช้เลขดิจิตที่เป็นตัวอักษรหรือสัญลักษณะอื่นๆ แต่จะทำให้จำนวนถังมากขึ้น เช่น ตัวอักษรภาษาอังกฤษต้องใช้ 26 ถัง ทำให้ใช้พื้นที่หน่วยความจำมากขึ้นด้วย

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s