Google         youtube            psv            สพม.11

การเรียงลำดับแบบนับจำนวน

                การจัดเรียงลำดับที่ผ่านมาเป็นการเปรียบเทียบค่าที่ใช้เวลาทำงาน O(n2) และ O(n Log n) สำหรับการเรียงลำดับแบบนับจำนวนหรือการเรียงลำดับแบบยอดรวมสูงสุด (Tally Sort) จะไม่มีการเปรียบเทียบค่าและใช้เวลาทำงาน O(n) เป็นการนับแต่ละค่ามีจำนวนเท่าไรและนำมาจัดเรียงตามลำดับ มีลักษณะการจัดเรียงลำดับแบบกระจาย (Distribution Sort) เช่นเดียวกับการเรียงลำดับแบบเรดิกซ์ เหมาะกับการเก็บค่าที่ซ้ำกันมากๆ เช่น ต้องการจัดเรียงเรคคอร์ดนักศึกษาโดยแบ่งออกตามสาขาที่เรียน คือ บัญชี (ACC) คอมพิวเตอร์ธุรกิจ (BCO) การตลาด (MKT) และใช้หลักการยอดรวมสูงสุดนับจำนวนนักศึกษาของแต่ละสาขา โดยสาขาบัญชีมี 214 คน  สาขาคอมพิวเตอร์ธุรกิจมี 529 คน สาขาการตลาดมี 385 คน ดังนั้นจัดเรียงเรคคอร์ดสาขาบัญชีอยู่ในกลุ่ม a0…213 สาขาคอมพิวเตอร์ธุรกิจอยู่ในกลุ่ม a214…742  สาขาการตลาดอยู่ในกลุ่ม a742…1127   ดังนั้น อัลกอริทึมในการจัดเรียงลำดับแบบนับจำนวนได้เป็นดังในตารางที่ 11.16

ตารางที่ 11.16  อัลกอริมทึมการเรียงลำดับแบบนับจำนวน

  1. สร้างอาร์เรย์ count เพื่อเก็บความแตกต่างของค่าในกลุ่ม (Sequence) โดย count = {c0, c1, c2,…,cm-1}
  2. นับจำนวนของแต่ละค่าเก็บในอาร์เรย์ count โดยแต่ละ Ck  เป็นจำนวนของค่าที่เท่ากับ k
  3. คำนวณค่าในอาร์เรย์ count แบบสะสมเพิ่มขึ้น จะได้แต่ละ Ck เป็นค่าที่น้อยกว่าหรือเท่ากับ k
  4. สร้างอาร์เรย์ชั่วคราว aTemp โดย aTemp = {b0, b1, b2,…,bn-1 }
  5. ตั้งแต่ i = n-1  จนถึง i = 0 คัดลอกค่า ai  ให้กับ bj และลดค่าของ Ck  หนึ่งค่าเมื่อ j = ck  และ k = ai
  6. คัดลอกค่าทั้งหมดในอาร์เรย์ชั่วคราว b กลับไปยังอาร์เรย์ a

การ เรียงลำดับแบบนับจำนวนแบ่งการทำงานออกเป็น 2 ช่วง คือ ช่วงการนับจำนวนของแต่ละค่ามีเท่าใด กับช่วงกระจายค่าเก็บไว้ในอาร์เรย์ชั่วคราวและคัดลอกค่าที่เรียงตามลำดับ กลับมาที่อาร์เรย์ต้นทาง การทำงานแต่ละขั้นตอนใช้เวลา O(n) หรือ O(n2)  ซึ่ง m เป็นค่าคงที่ (Constant) และเขียนเป็นฟังก์ชันได้เป็นตารางที่ 11.17

ตารางที่ 11.17  ฟังก์ชันเรียงลำดับแบบนับจำนวน

Void countingSort  ( int key[], int size, int m ){
int i, k;
int *count = malloc( sizeof(int)*m );
int *aTemp = malloc( sizeof(int)*size );

for( i = 0; i < m; i++)
count[i] = 0;
for( i = 0; i < size; i++)
++count[ key[i] ];

for( k = l; k < m; k++)
count[k] += count[k-1];

for( i = size-l; i >= 0; i–){
aTemp[ –count[ key[I ] ] ] = key[i];
}
For( i = 0; i<size; i++)=””>
key[i] = aTemp[i];
ตัวอย่างการเรียงลำดับแบบนับจำนวนจะใช้อาร์เรย์ที่มีการเก็บค่าซ้ำกัน คือ {2,1,2,0,1,1,0,2,1,1} มีทั้งหมด n = 10 ค่า โดยมีจำนวนความแตกต่างของค่าคือ m = 3 (0,1,2) จากนั้นนับจำนวนยอดรวมของแต่ละค่าเก็บไว้ในอาร์เรย์ count = {2,5,3} หมายถึงค่า 0 มีจำนวน 2 ค่า ค่า 1 มีจำนวน 5 ค่า และค่า 2 มีจำนวน 3 ค่า จะเห็นว่าค่าที่ถูกนับจะเป็นดัชนีของอาร์เรย์ count จากนั้นทำการสะสมค่าเพิ่มโดยนำค่าก่อนหน้ามารวมกัน ค่าในอาร์เรย์ count ได้เป็น {2,7,10} (2,2+5,7+3) หมายถึง มี 2 ค่าน้อยกว่าหรือเท่ากับ 0 มี 7 ค่าน้อยกว่าหรือเท่ากับ 1 และมีค่าน้อยกว่าหรือเท่ากับ 2

หลังจากทราบ จำนวนยอดรวมสะสมเพิ่มของแต่ละค่าเก็บไว้ในอาร์เรย์ count ก็เป็นการกระจายค่าเก็บไว้ในอาร์เรย์ชั่วคราว ดังในรูปที่ 11.16 ในการกระจายใช้นิพจน์ aTemp[- -count[ key [i] ] ] = key[i]; เป็นการนำค่าของ key[i] มาเป็นดัชนีของอาร์เรย์ count และได้ค่าในตำแหน่งนั้นมาพร้อมกับลดค่าลงหนึ่งค่า นำไปเป็นดัชนีของอาร์เรย์ atemp ซึ่งเป็นตำแหน่งที่จะนำค่าของ key [i] มาเก็บไว้ เช่น ครั้งแรกใช้ key[9]=1 จะได้ count[1]=7-1 เหลือ 6 และได้ aTemp[6] เก็บค่า 1 ครั้งแรกใช้ key ใช้ key[8]=1 จะได้ count[1]=6-1 เหลือ 5 และได้ aTemp[5] เก็บค่า 1 เมื่อกระจายค่าถึง key [9] ครบทุกค่าจะเป็นการคัดลอกค่ากลับไปยังอาร์เรย์ที่เป็นต้นแบบ
key

2

1

2

0

1

1

0

2

1

1

0

0

1

1

1

1

1

2

2

2

0

1

2

3

4

5

6

7

8

9

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

                จะเห็นว่าการกระจายค่าเป็นการทำงานถอยกลับจากค่า n-1 จนเหลือ 0 เพื่อเป็นการรับรองว่าค่าที่เท่ากันยังคงเรียงลำดับเช่นเดิมและเรียกว่าสเต เบิ้ล (Stable) ดังที่กล่าวในตอนต้นบท นอกจากนี้จะเห็นว่าค่าที่อยู่ใน key ต้องเป็นค่าระหว่าง {0,1…,m-1} จึงจะใช้ได้เนื่องจากนำไปใช้เป็นดัชนีของอาร์เรย์ count หากเป็นค่ารูปแบบอื่น เช่น สตริง ACC, BCC, MKT จะต้องใช้ฟังก์ชันแปลงค่า h(ACC) = 0, h(BCO)=1, h(MKT)=2

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