บทที่ 11

          การจัดเรียงลำดับข้อมูล

วัตถุประสงค์เชิงพฤติกรรม (Behavioral Objective)
หลังจากศึกษาจบบทเรียนนี้แล้ว นักศึกษาจะมีความสามารถดังนี้
(After studying this chapter, you will be able to)

  1. อธิบายการเรียงลำดับภายใน
  2. สรุปการเรียงลำดับภายนอก
  3. ศึกษา/ปฏิบัติการเรียงลำดับแบบบับเบิ้ล
  4. แสดงตัวอย่างการเรียงลำดับแบบเลือก
  5. แสดงตัวอย่างการเรียงลำดับแบบแทรก
  6. ปฏิบัติการเรียงลำดับแบบเซลล์
  7. ปฏิบัติการเรียงลำดับแบบผสาน
  8. ปฏิบัติการเรียงลำดับแบบรวดเร็ว
  9. ปฏิบัติการเรียงลำดับแบบฮีพ
  10. ปฏิบัติการเรียงลำดับแบบนับจำนวน
  11. ปฏิบัติการเรียงลำดับแบบเรดิกซ์
  12. ปฏิบัติการเรียงลำดับและผสานแฟ้มข้อมูล
  13. แสดงตัวอย่างการเรียงลำดับและผสานสมดุล
  14. แสดงตัวอย่างการเรียงลำดับและผสานหลายขั้นตอน
  15. จัดบอร์ดเชิงปฏิบัติการ “การเรียงลำดับข้อมูล”
  16. สนทนาเชิงปฏิบัติการ “การเรียงลำดับแบบรวดเร็ว”
  17. อธิบายคำศัพท์ได้ 15 คำ

 

 

     

 

 

                         สำหรับบทนี้เป็นการกล่าวถึงเทคนิคในการสร้างจัดเรียงรับดับข้อมูล(Sortinq) ซึ่งเป็นกระบวนการที่คล้ายกับเทคนิค ในการค้นหาค่าข้อมูล(Record)ที่จะกล่าวในบทต่อไปการจัดเรียงในรับดับค่าของข้อมูลจะพิจารณาถึงรับดับก่อนหน้าและหลังแต่ละเรคคคอร์ดหรือทะเบียน(Recorf) โดยมีคีย์ที่นำมาใช้พิจารณาถึงรับดับก่อนหน้าและหลังของแต่ละเรคคอร์ดเพื่อประสิทธิ์ภาพการทำงานและง่ายต่อการเรียกใช้งาน การเรียงลำดับข้อมูลจึงเป็นกระบวนการเพื่อจัดการเรคคอร์ดให้จัดเรียงลำดับตามคีย์ เป็นเทคนิคในการค้นหาข้อมูลมีประสิทธ์ภาพมากขึ้น โดยมีการออกเป็น 2 ประเภทๆ หลักคือ
การเรียงลำดับภายใน
                 การเรียงลำดับภายใน(Internal Sorting) เป็นหลักการทีมาใช้เมื่อนำข้อมูลทั้งหมดที่รวบรวมไว้มีขนาดเล็กเพียงพอ ที่จะเก็บไว้ และ ทำการเรียงลำดับภายในหน่วยความจำหลัก(Memorly) เวลาที่มักใช้ในการอ่านและเขียนเรคคอร์ดจะนำใช้พิจารณาถึงประสิทธิ์ภาพการเรียงลำดับข้อมูล แต่จะใช้เวลาในการเปรียบเทียบค่าของคีย์มาพิจารณา นอกจากนี้การเรียงลำดับภายในยังแบ่งออกเป็น2 ลักษณะ คือ การเรียงลำดับข้อมูลที่ใช้เฉพาะพื้นที่หน่วยความจำของ ตนเอง(Inplace Sort) และการเรียงลำดับข้อมูลที่ต้องใช้พื้นที่หน่วย ความจำเพิ่มเติมเข้ามาช่วยจัดเรียง
การเรียงลำดับภายนอก
                การเรียงลำดับภายนอก(External Sortinq) เป็นหลักการที่นำมาใช้กับข้อมูลที่รวบรวมไว้เป็นจำนวนมากๆ ไม่สามารถเก็บไว้ในหน่วยความจำหลักได้หมดในคราวเดียวกัน แต่ต้องเก็บไว้ในหน่วย
ความจำหลักได้หมด ในคราวเดียวกัน แต่ต้องเก็บไว้ในหน่วยสำรอง เช่น เทปแม่เหล็กหรือจานแม่เหล็ก การเรียงข้อมูลจะกระทำได้พียงบางส่วน ในแต่ละครั้ง ประสิทธิ์ภาพในการเรียงลำดับแบบนี้จึงพิจารณาจากเวลาที่ใช้อ่านและเขียน เพื่อถ่ายโอนข้อมูลระหว่างความจำหลักกับความจำสำรอง
                    บางครั้งการเรียงลำดับการใช้กับเรคคอร์ดที่ค่าของคีย์ซ้ำกันได้ ทำให้กอริทึมการเรียง
ดับเรียกว่า สเตเปิ้ล(Stable Sort) เมื่อลำดับเรคคอร์ดที่มีค่าของคีย์ซ้ำกันได้เกมือนเดิมหลังจากการมีเรียงลำ เช่น เรคคอร์ด ที่ 5 และ 8 มีค่าของคีย์เท่ากัน หลังจากที่เรียงลำดับแล้วเรคคร์ดที่ 5 ยังคงมาก่อนเรคคอร์ดที่ 8 เหมือนจึงเรียกว่า การเรียงลำดับแบบสเตเบิ้ล แต่ถ้าหากเรคคอร์ดที่ 5 ไปอยู่หลังเรคคอร์ดที่ 8จะไม่เป็นสเตเบิ้ล การเรียงลำดับแบบสเตเบิ้ลมาใช้  เมื่อลำดับเดิมยังมีความสำคัญหรือมีความหมายบางอย่างในการใช้งาน เช่น การเรียงลำดับเรคคอร์ด ตามค่าของคีย์แต่คำนึงถึงเวลาของแต่ละคอร์ดที่บันทึกไว้
                      การเรียงลำดับข้อมูลนำมาใช้การจัดเรียงลำดับเรคคอร์ดตามค่าของคีย์ในแฟ้มข้อมูล(Fill)
ซึ่งส่วนใหญ่อัลกอริทึม ที่ใช้เป้ฯการเรียงลำดับมีการเปรียบเทียบ(Comparieon Sort) และในที่นี้จะใช้เป็นคีย์อย่างเดียวสำหรับการเรียงลำดับข้อมูลและเก็บอยู่ของอาร์เรย์มีการเปรียบอยู่สองค่าของสมาชิกของอาร์เรย์การเรียงลำดับตามค่าของคีย์  อาจใช้เป็นแบบจากค่าน้อยไปหามาก (Ascendinq) หรือให้เรียงลำดับจากค่ามากไปหาค่าน้อย(Desendinq) สำหรับการเรียงลำดับภายในจะใช้การเรียงลำดับมีการเรียงลำดับมีการเปรียบเทียบมาพิจารณาถึงประสิทธิ์ภาพ ซึ่งใช้เวลาน้อยที่สุดคือ O(n loq n) ขณะที่การเรียงลำดับมีการ       เปรียบเทียบ จะใช้เวลาน้อยที่สุด คือ O(n) ส่วนการเรียงลำดับภายนอกถึงแม้ใช้การเรียงลำดับมีการเปรียบเทียบแต่ใช้เวลาการทำงานน้อยกว่าเมื่อเทียบเวลาการทำงานของ I/O เพื่ออ่านและเขียนข้อมูลระหว่างหน่วยความจำหลักกับหน่วยความจำสำรองจึงไม่นำมาพิจารณา ในการเรียงลำดับข้อมูลจึงมีเทคนิคหรือวิธีอื่นๆมากมายซึ่งแบ่งออกเป็นประเภทต่างๆ ตามประสิทธิ์ภพการทำงาน ดั้งต่อไปนี้

         1. การเรียงลำดับมีการเปรียบเทียบ O(n2)
การเรียงลำดับแบบดับเบิ้ล  (Bubble Sort)
การเรียงลำดับแบเลือก  (Selection Sort)
การเรียงลำดับแบแทรก  (Insertion Sort)
การเรียงลำดับแบบเชล์   (Shell Sort)
     2.การเรียงลำดับมีการเปรียบเทียบ O(n Loq n)
การเรียงลำดับแบบผสาน  (Merqe Sort)
การเรียงลำดับแบบรวดเร็ว  (Quick Sort)
การเรียงลำดับแบบฮีพ  (Heap Sort)
     3.การเรียงลำดับไม่มีการเปรียบเทียบ
การเรียงลำดับแบบนับจำนวน(Countinq Sort)
     4.การเรียงลำดับและผสานแฟ้มข้อมูล
การเรียงลำกับแบบบับเบิ้ล
        เป็นอัลกอริทึม การจัดเรียงลำดับข้อมูลที่เป็นมาตรฐานโดยการทำงานเป็นการเปรียบเทียบค่าสมาชิกของอาร์เรย์ที่อยู่ติดกันและมีการสลับตำแหน่งกันเมื่อค่าทั้งสองไม่เรียงลำดับในลักษณะที่เปรียบเทียบทีลพคู่ตามลำดับจากคู่ที่อยู่ด้านซ้ายไปยังด้านขวาค่าที่มากที่สุดจะย้ายไปยังส่วนท้ายของอาร์เรย์จากการเปรียบเทียบและขยับทีละตำแหน่ง เช่นเดียวกับฟองอากาศน้ำ ฟองที่ใหญ่กว่าจะลอยชนฟองที่เล็กกว่า แทรกไปยังผิวน้ำ
             ในรอบแรกการทำงานจะย้ายค่ามากที่สุดไปยังส่วนท้ายของอาร์เรย์ หลังจากนั้นทำแบบเดิมกับส่วนย่อยของอาร์เรย์  คือ n-1 ที่ยังไม่เรียงลำดับ นำค่ามากที่สุดรองลงมาไปไว้ยังตำแหน่ง ที่ถูต้อง และเรียงตามลำดับแบบบับเบิ้ลดั้งใน
ตารางที่ 11.1 อัลกอริทึมการเรียงลำดับแบบบับเบิ้ล


1.      ทำขั้นตอน 2 ซ้ำ ตั้งแต่ i=n-1 จนถึง i=1
2.   ทำขั้นตอน 3 ซ้ำ ตั้งแต่   j=0  จนถึง  j=i-1
3.   ถ้าค่า a,น้อยกว่า aj+1  ให้สลับตำแหน่งกัน

และเขียนเป็นฟังก์ชันเรียงลำดับแบบบับเบิ้ลได้เป็น  ตารางที่11.2
ตารางที่ 11.2 ฟังก์ชันเรียงลำดับแบบบับเบิ้ล


Void   bubblesort  (int key[], int size){
           Int i, j;
           For ( i=size-1;  i>0; i--)
           If (Key[j]>key[j+1])
                Swap(&key[j],&key[j+1]);

 

เมื่อนำการเรียงลำดับแบบบับเบิ้ลมาใช้กับอาร์เรย์ที่มีสมาชิก (66,33,99,88,44,55,2,77)  จะมีขั้นตอนดั้งในรูปที่  11.1 โดยรูปภายในจะทำการย้ายค่าที่มากที่สุดไปไว้ยังตำแหน่งที่ถูกต้องในแต่ละรอบโดยการสลับตำแหน่งที่ติดกัน ส่วนรูปภายนอกเป็นการกำหนดรอบให้มีการหนดรอบให้มีการย้ายทุกๆค่าในอาร์เรย์ ซึ่งมีสมาชิก n=8 จึงมีการทำงาน n-1=7รอบ เช่น ในระบบแรกจะ  นำค่าติดกัน ส่วนรูปภายนอกเป็นการกำหนดรอบให้มีการย้ายๆทุกๆ ค่าในอาร์เรย์ซึ่งมีสมาชิก n = 8 จึงมีการทำงาน n-1=7 รอบ เช่น ในรอบแรกจะนำค่าที่ติดกันมาเปรียบเทียบกันที่ละคู่ทั้งหมดในอาร์เรย์ ค่าที่มากว่าจะถูกขยับไปเรื่อยๆ จนถึงสุดท้ายของอาร์เรย์หลังจากนั้นในรอบถัดไปก็ทำเฉพาะในส่วนที่เหลือ  และจำนวนการทำซ้ำจะลดลงตามจำนวนค่าเหลือเพียงค่าเดียวก็ไม่ต้องทำต่อจบการทำงาน 

ทำงาน                                                                    
0


66

33

99

88

44

55

22

77

33

33

99

88

44

55

22

77

33

33

99

88

44

55

22

77

33

33

88

99

44

55

22

77

33

33

99

44

99

55

22

77

33

33

99

44

55

99

22

77

33

33

99

44

55

22

99

77

33

33

99

44

55

22

77

99

                          0
                          1
                          2
                          3
                         4
                          5
                          6
                          7                         

                                                 รอบที่ 1
                                                                                 


33

66

88

44

55

22

77

99

33

66

88

44

55

22

77

99

33

66

88

44

55

22

77

99

33

66

44

88

55

22

77

99

33

66

44

55

88

22

77

99

33

66

44

55

22

88

77

99

33

66

44

55

22

77

88

99

                              0
                         1
                         2   
                         3
                        4
                        5
                        6
                                              

                                                 รอบที่ 2

33

66

44

55

22

77

88

99

33

66

44

55

22

77

88

99

33

44

66

55

22

77

88

99

33

44

55

66

22

77

88

99

33

44

55

22

66

77

88

99

33

44

55

22

66

77

88

99

                                                                                 
                         0
                        1
                        2    
                        3
                        4
                        5
                    
                                              

                                                 รอบที่ 3

33

44

55

22

66

77

88

99

33

44

55

22

66

77

88

99

33

44

55

22

66

77

88

99

33

44

22

55

66

77

88

99

33

44

22

55

66

77

88

99

                                                                                 
                          0
                          1
                          2   
                          3
                         4
                    
                                                                                     รอบที่ 4
                                              

                                                

33

44

22

55

66

77

88

99

33

44

22

44

66

77

88

99

33

22

44

55

66

77

88

99

33

22

44

55

66

77

88

99

                                                                                 
                         0
                        1
                        2   
                        3
                    
                                                                                     รอบที่ 5

 

33

22

44

55

66

77

88

99

22

33

44

55

66

77

88

99

22

33

44

55

66

77

88

99

                                                                                 
                         0
                        1
                        2   
                     
                    
                                                                                     รอบที่ 6


22

33

44

55

66

77

88

99

22

33

44

55

66

77

88

99

                                                                                 
                         0
                        1
                    
                                                                                    รอบที่ 7               

                              รูปที่ 11.1 ขั้นตอนการเรียนลำกับข้อมูลแบบบับเบิ้ล  

 

                    ในแต่ละรอบในการทำงานหลังจากเปรียบเทียบค่าแจมีการสลับตำแหน่งของค่าอาจมีการสลับตำแหน่งของค่าที่ไม่โรงเรียนตามลำดับ ซึ่งจะใช้ฟังก์ชัน swap  ให้การสลับตำแหน่งดั้งในตารางที่ 11.3  
ตาราง 11.3 ฟังก์ชันการสลับตำแหน่ง


Void swap (int *l, int &r){
 Int tmp=*l;
*L=*R;
*R=tmp;

                ประสิทธิภาพการจัดเรียงแบบบับเบิ้ลพิจารณาได้จากตารางที่11.2 ลูปภายนอกมีการทำงาน n-1 ครั้งโดยตัวแปร I ทำงานจากค่า 0 จนถึง i=1 และการวนซ้ำแต่ละครั้งมีการเปรียบเทียบค่าทั้งหมดจึงเท่ากับ
(n-1)+(n-2)+(n-3)+…..+3+2+1
ผลรวมทั้งหมดเท่ากับ(n(n-1)/2ถ้าหากค่า n มีขนาดใหญ่มากการทำงานจะเข้าใกล้ n2/2 จะอยู่ในรูปแบบของ n2 ซึ่งทำให้การจัดเรียงรับดับแบบบับเบิ้ลมีการเปรียบเทียบเป็น 0(n2)จำนวนการทำงานจะเพิ่มขึ้นเป็นยกกำลังสอง (Quabratic) หมายความว่า ขนาดของอาร์เรย์เพิ่มขึ้นเป็น2เท่า และจำนวนครั้งในการทำงาน จะเพิ่มขึ้นเป็นสี่เท่า
                           การเรียงลำดับแบบเลือก
                เช่นเดียวดับดารจัดเรียงลำดับแบบบับเบิ้ลซึ่งการทำงานจะมีจำนวน n=1 รอบและทำการเปรียบเทียบค่าทั้งหมดตามลำดับอาร์เรย์ โดยแต่ละตั้งจะมีการย้ายค่ามากที่วุดของค่าที่เหลือที่ยังจัดเรียงตามลำดับไปยังที่ตำแหน่งที่ถูกต้อง ดั้งในรูปที่ 11.2ลักษณะการทำงานจะมีประสิทธิภาพมากกว่าการจัดเรียงลำดับแบบบับเกิ้ล ที่ในแต่ละรอบการทำงานจะมีการสลับตำแหน่งเพียงครั้งเดียว และได้อัลกอริทึมการเรียงลำดับแบบเลือกตั้งในตาราง ตารางที่ 11.4 อัลกอริทึมการเรียงลำดับแบบเลือก

1. ทำขั้นตอน 2ซ้ำแต่ i=n-1จนถึง i=1
2. ทำการสลับตำแหน่งระหว่าง a กันค่าที่มากที่สุดใน [ao…ai]

และเขียนเป็นฟังก์ชันเรียงลพดับแบบเลือกได้เป็นตารางที่ 11.5

ตารางที่ 11.5 ฟังชันก์เรียงลำดับแบบเลือก


Void Selectionsort  (int key [], I nt size){
         Int I, j, max;
         For(i=size-1; i>0; i--){
         Max =0;
         For (j=1; j ,=I; j++)
         If(key[j]>key[max])
         Max=j;
         Swap(&key[max]);
         }
}

 

 

 

 

 

                 เมื่อนำลำดับแบบเลือกมาใช้กับอาร์เรย์ตัวเดียวกับตัวอย่างในการเรียงลำดับแบบบับเบิ้ลซึ่งมีสมาชิกn=8มีขั้นตอนดั้งในรูปที่ 11.3 โดยรูปภายนอกทำงาน n-1=7 รอบ ในแต่ละรอบจะมีการสลับตำแหน่งเพียงครั้งเดียวหลังจากพบค่าที่มากที่สุดเพื่อนำไปใช้ในตำแหน่งที่ถูกต้อง ในรอบแรกหลังจากการเปรียบเทียบค่าทั้งหมดพบว่าค่าที่มากที่สุดคือ 99 ในตำแหน่งอาร์เรย์ที่2  ก็ทำการสลับตำแหน่งกับค่า 77 ในตำแหน่งอาร์เรย์ที่ 7 หลังจากนั้นในรอบถัดไปก็ทำแบบเดิมกับค่าที่เหลือ จำนวนค่าที่เหลือก็ลดน้อยลงจนเหลือเพียงค่าเดียว ก็ไม่ต้องทำต่อจนจบการทำงาน


66

33

99

88

44

55

22

77

66

33

77

88

44

55

22

99

 

                    
รอบที่ 1


66

33

77

88

44

55

22

99

66

33

77

22

44

55

88

99

 

                                                       รอบที่ 2


66

33

77

22

44

55

88

99

66

33

55

22

44

77

88

99

                                                                                      

 

รอบที่ 3


66

33

55

22

44

77

88

99

44

33

55

22

66

77

88

99

 

รอบที่ 4


44

33

55

22

66

77

88

99

44

33

22

55

66

77

88

99

 

รอบที่ 5


44

33

22

55

66

77

88

99

22

33

44

55

66

77

88

99

 

รอบที่ 6


22

33

44

55

66

77

88

99

22

33

44

55

66

77

88

99

 

รอบที่7
รูปที่ 11.3ขั้นตอนการเรียงลำดับข้อมูลแบบเลือก

 

                 การจัดเรียงลำดับแบบเลือกมีการเปรียบเทียบเป็น o(n2)จำนวนการทำงานจะเพิ่มขึ้น เป็นยกกำลังสองเช่นกับการ จัดเรียงลำแบบบับเบิ้ล แต่จะทำงานได้เร็วกว่าเนื่องจากการย้ายค่าจะใช้เพียงo(n2)ในแต่ละรอบ จากตัวอย่างของทั้งสองแบบจะเห็นว่ามีการเปรียบค่าเท่ากัน คือ 28 (7+6+5+4+3+2+1)แต่การเรียงลำดับแบบบับเบิ้ลมีกาวรสลับบตำแหน่ง 16 ครั้ง ส่วนการจัดเรียงลำดับแบบเลือกสลับตำแหน่งเพียง 7 ครั้ง 
การเรียงลำดับแบบแทรก
          เช่นเดียวกับการจัดเรียงลำดับทั้งสองแบบที่ผ่านมาซึ่งการทำงานมีจำนวน n-1 รอบและเปรียบเทียบข้อทั้งหมดตามลำดับในอาร์เรย์ โดยแต่ระรอกบมีการแทรกค่าถัดไปเข้าในอาร์เรย์ย่อยด้านซ้าย และเป็นได้อาร์เรย์ย่อยด้านซ้าย และได้เป็นได้อาร์เรย์ย่อยที่จัดเรียงตามลำดับ ทีลักษณะแบบเดียวกับผู้เล่นไพ่ เมื่อได้รับไพ่จากการแจกก็จะนำมาแทรกไว้ในไพ่ที่ถืออยู่เพื่อให้ตัวเลขเรียงตามลำดับและต้องมีการขยับไพ่ใบอื่นหรือตำแหน่งให้ถูกต้อง ดั้งในรูปที่ 11.4 และได้อัลกอริทึมการเรียงลำดับแบบแทรก
ตารางที่ 11.6 อัลกอริทึมการเรียงลำดับแบบแทรก


1.ทำขั้นตอน 2-5ซ้ำตั้งแต่ i=1จนถึง i=n-1
2. เก็บค่าของajไว้ที่ตัวแปลชั่วคราว
3.ค้นหาที่ดัชนี j_<I สำหรับค่า aj_>ai
4.ขยะค่าจากอาร์เรย์ย่อย {aj…ai-1} หนึ่งตำแหน่งไปยัง {aj+1…a}
5.นำค่าในตัวแปลชั่วคราวซึ่งเป็นของ ai ให้กับaj

 และเขียนเป็นฟังก์ชันแบบแทรก ได้เป็นตารางที่ 11.7
ตารางที่ 11.7 ฟังก์ชันเรียงลำดับแบบแทรก


Void insertionsort (int key[], int  size){
         Int I, j, insert;
         For(i=1;i<size;i++){
         Insert=key[i];
         For(j=I;(j<0)&&(key[j-1]>insert);j--)
         Key[j]=key[j-1];
         Key[j]=insert;
         }
}

ตัวอย่างการเรียงลำดับแบบแทรกจะใช้อาร์เรย์ตัวเดียวกับที่ผ่านมาซึ่งมีสมาชิก n=8 และมีขั้นตอนดั้งในรูปที่ 11.5 โดยรูปภายนอกทำงาน 7รอบ ในแต่ระรอบจะมีการนำค่าตำแหน่งที่ยังมีค่าน้อยกว่า และค่าที่มากว่าจะขยับเข้ามาทางขวาหนึ่งตำแหน่ง หากมีค่ามากกว่าก็จะพบตำแหน่งที่ถูกต้องและเก็บค่าในตำแหน่งนั้น เช่น ในรอบที่ 4 ต้องการแทรกค่า 44 ในตำแหน่งอาร์เรย์ที่ 4 ไปทางซ้าย หลังจากเปรียบเทียบที่ละ ค่าจะพบตำแหน่งที่ถูกต้องอยู่ในตำแหน่งอาร์เรย์ที่ 1 ก็ทำการเก็บค่าซึ่งได้จากตัวแปล insret ในรอบถัดไปก็ทำค่าแบบเดิมกับค่าแบบเดิมกับค่าที่เหลือ จนกระทั่งทุกค่าถูกแทรกเข้าไปจนครบจึงจบการทำงาน

 

 

66

33

99

88

44

55

22

77

33

66

99

88

44

55

22

77

 

                                                  รอบที่ 1


33

66

99

88

44

55

22

77

33

66

99

88

44

55

22

77

                                                     

                                                 รอบที่ 2
                       


33

66

99

88

44

55

22

77

33

66

88

99

44

55

22

77

 

                                              
                                                                          รอบที่ 3


33

66

88

99

44

55

22

77

33

44

66

88

99

55

22

77

 

                                                                          รอบที่ 4

33

44

66

88

99

55

22

77

33

44

55

66

88

99

22

77

 

                                                 รอบที่ 5

33

44

66

55

88

99

22

77

22

33

44

55

66

88

99

77

 

                                                                          รอบที่ 6

22

33

44

55

66

88

99

77

22

33

44

55

66

77

88

99

 

                                                                          รอบที่7
                                                   รูปที่ 11.5 ขั้นตอนการเรียงลำดับข้อมูลแบบแทรก

                       ลักษณะการทำงานของการเรียงลำดับแบบแทรกจะเป็นการหมุนไปทางขวา(Reqit Rotation) ของค่าบางส่วนหรือดลุ่มย่อยของคำ(Seqment) ในอาร์เรย์ดั้งในรูปที่ 11.6 เป็นรอบที่ 4 ในตำแหน่งอาร์เรย์ที่ 1ถึงตำแหน่งอาร์เรย์ที่ 4แต่ละค่าจะหมุนไปทางขวาหนึ่งตำแหน่งค่าที่อยู่ขวาสุดจะหมุนไปซ้ายสุด ก็จะเกิดเรียงตามลำดับ
                       เช่นเดียวกับการจัดเรียงลำดับแบบบับเบิ้ลและแบบเลือก การทำงานมีจำนวน n-1 รอบแต่ละรอบจะมีการหมุนเซ็กเม้นท์ในอาร์เรย์ การหมุนแต่ละครั้งอาจหมุนค่าตั้งแต่ละครั้งอาจหมุนค่าตั้งแต่ 1ถึง n ค่า และมีจำนวนการเปรียบเทียบค่าซึ่งเป็นค่าที่มีเซ็กเม้นโดยเฉลี่ยการหมุนจะเป็นครึ่งของความยาวเซ็กเม้นทื่ค่าถูกเรียงลำดับก่อนหน้านี้ความยาวเฉลี่ยของเซ็กเม้นท์จึงเท่ากับ n/2 และจำนวนในการเปรียบเทียบค่าเป็น n/4  ดั้งนั้นในกรณีเฉลี่ย (Averaqe Case) มีการเปรียบเทียบค่าเท่ากับ(n/4)(n-1) และในกรณีแย่ที่สุด(Worfst Case) มีการเปรียบเทียบค่าเท่ากับ (n/2)(n-1)
                 เนื่องจากการจัดเรียงลำดับแบบแทรกไม่มีการสลับตำแหน่งเช่นเดียวกับการจัดการเรียงลำดับทั้งสองแบบที่พ่านมา จึงใช้การย้ายในการเปรียบเทียบกัน โดยการหมุน 4 ค่าเท่ากับ การย้ายค่า 4 ค่าจากตัวอย่างการจัดเรียงลำดับแบบบับเบิ้ลมีการย้ายค่า 32 ค่า ซึ่งไม่จำเป็นเสมอไปเนื่องจากการแบบแทรกมีการเปรียบเทียบค่าเท่ากับ (n/2)(n/1)ในทุกกรณี แต่ในกรณีเฉลี่ยของแบบแทรกจะเร็วกว่าเป็นสองเท่า คือ (n/4)(n/1)
                 อย่างไรก็ตาม ในกรณีเฉลี่ยแย่ที่สุดของการเรียงลำดับแบบแทรกมีการเปรียบเทียบส่วนกรณีดีที่สุด (Best Case) มีการเปรียบเทียบเป็น o(n) โดยใช้เวลาเป็นเส้นตรงและเกิดขึ้นเมื่อแต่ละรอบมีการเปรียบเทียบค่าเพียงครั้งเดียว ซึ่งหมายถึงทุกๆ ค่าในอาร์เรย์มีการจัดเรียงลำดับก่อนเรียบร้อยแล้ว
                           การทำงานอัลกอริทึมเป็นกานหาตำแหน่งที่ถูกค่าให้ค่าในลักษณะที่เป็นการหารตามลำดับต่อเนื่องจึงเรียกว่าการเรียงลำดับแนวตรง( Binary Insertion Sort) ซึ่งเป็นตังอย่างการใช้ไบนารี่ที่11.6 การเรียงลำดับแบบเชล์
               การเรียงลำดับแบบแทรกใช้เวลาเป็นเส้นตรงเมื่ออาร์เรย์ทีการจัดเรียงลำดับก่อนแล้วเท่านั้น สิ่งสำคัญคือการจัดเรียงลำดับที่ใช้เวลา เกือบเป็นเส้นตรงเมื่ออาร์เรย์เกือบจัดเรียงลำดับที่เสร็จเรียบร้อยแล้ว  ซึ่งค้นพบโดย Donald Shell และแสดงได้เห็นว่าการจัดเรียงลำดับบนอาร์เรย์สามารถทำได้ดีกว่าเวลาที่ใช้เป็นยกกำลังสอง
                      การจัดเรียงลำดับแบบเซล์หรือจำนวนลำดับแบบจำนวนเพิ่มๆค่อยลดลง (Diminishing Incremeny Sort จะใช้เรียงลำดับแบบแทรกกับกลุ่มย่อยของค่าตาม
ดับ กลุ่มย่อยเหล่านี้จะถูกเลือกใช้ในทิศทางพยายามให้ค่าถูกเรียงมากสุดก่อนที่จะใช้ การเรียงลำดับแบบแทรก ก็จะได้เวลาการทำงานที่ใช้การเรียงลำดับแบบแทรกในแต่ละรอบเกือบเป็นเส้นตรง
                      กลุ่มย่อยจะถูกกำหนดด้วยตัวเลขในการกระโดดข้าม (Skip Number) และค่าที่อยู่ในกลุ่มย่อยเดียวกันก็จะห่างกันเท่าตัวเลข กระโดดข้ามคือ d=4 ก็จะได้ 4 กลุ่มย่อยที่ถูกจัดเรียงลำดับและความเป็นอิสระ ต่อกันไม่เกี่ยวข้อง ดั้งนี้
{S0, S4, S8,S12,…}
{S1, S5, S9,S13,…}
{S2, S6, S10,S14,…}
{S3, S7, S11,S15,…}       

แต่ละกลุ่มย่อยของทั้ง 4 กลุ่มสามารถถูกจัดเรียงลำดับที่เป็นอิสระต่อกัน โดยใช้โปรเซทเซอร์แยกกันและทำงานเป็นแบบขนาน  (parallelizable) อัลกอริทึมการเรียงลำดับแบบเซลล์เป็นได้ดั้งนี้ในตารางที่ 11.8
ตาราง ที่ 11.8 อัลกอริทึมการเรียงลำดับแบบเซลล์


1.ให้ d=n/2 เป้นตัวเลขกระโดดข้าม
2. ทำขั้นตอน 3-4 ซ้ำ เมื่อ d ยังมากว่า 0
3. ใช้การเรียงลำดับแบบแทรกกับแต่ละกลุ่มย่อย d กลุ่ม
     {S0, Sd, S2d,S12,…}
     {S1, Sd+1, S2d+1,S3d+1,…}
     {S2, Sd+2, S2d+2,S3d+2,…}
             .
             .
             .
     {Sd-1, S2d-1, S3d-1,S4d-1,…}
4.กำหนดให้ d=d/2

และเขียนลำดับฟังก์ชัน เรียงลำดับแบบเซลล์ได้เป็นตารางที่  11.9 แบ่งออกเป็นฟังชันก์ชัน shebllSort เป็นหลักเพื่อกำหนดตัวเลขกระโดดข้าม และฟังก์ชัน skipSort ใช้เรียงลำดับแบบแทรกค่าห่างกันเท่ากับ d ตำแหน่ง
ตารางที่ 11.9 ฟังก์ชันเรียงลำดับแบบเซลล์


Void skipSort (int key[],int size,int ,c, int d){
         Int I, j, k;
         For(i=c+d;i<size; i=d){
         K=key[i]
         J=1;
         While( (j> c)&&(key[j-d]>k)){
         Key[j]=key[j-d];
         j-=d;
}
         Key[j]=k;
}
Void shellSort (int key[], int size){
         Int d, j;
         For(d=asize/2;d>0;d/2)
         For (j=0; j<d; j++)
         skipSort(key,size, j ,d);
}

ตัวอย่างการเรียงลำดับ แบบเซลล์จะใช้เช่นเดียวกับที่ผ่าน โดยมีขั้นตอนดั้งใน รูปที่ 11.8 ในรอบเราแบ่งการทำงานออกเป็น 4 กลุ่มย่อย คือ {ao, a4},{a1, a5},{a2, a6},{ao, a4},เพื่อเรียงลำดับของแต่ละกลุ่ม ในรอบสุดท้ายค่าทั้งหมด จะถูกจัดเรียงตามลำดับ จะเห็นว่าแต่ละกลุ่มย่อยจะมีการย้ายค่าเพียงสองครั้งเท่านั้น

66

33

99

88

44

55

22

77

44

33

99

88

66

55

22

77

 

 

44

33

99

88

66

55

22

77

44

33

99

88

66

55

22

77

44

33

99

88

66

55

22

77

44

33

22

88

66

55

99

77

 

 

44

33

22

88

66

55

99

77

44

33

22

77

66

55

99

88

 

                                                     รอบที่ 1


22

33

22

77

66

55

99

88

44

33

22

77

66

55

99

88

 

 

22

33

22

77

66

55

99

88

22

33

44

55

66

77

99

88

 

  รอบที่ 2
                                             


22

33

44

55

66

77

99

88

22

33

44

55

66

77

99

88

 

                                                                               รอบที่ 3
รูปที่ 11.8 –ขั้นตอนการเรียงลำดับข้อมูลแบบเซลล์
โดยทั่วไปการแบ่งกลุ่มย่อยที่มีขนาด m จะมีการเปรียบเทียบค่าไม่เกิน m/2เนื่องจากครึ่งหนึ่งของจำนวนค่าได้ถูกจัดเรียงเรียบร้อยแล้วในรอบก่อนหน้านี้  เช่น ต้องการเรียงลำดับ ค่า n=128 ในรอบแรกมการจัดเรียงลำดับ4 กลุ่มย่อยที่มีขนาดเท่ากับ 2 รอบที่  32มีการเรียงลำดับกลุ่มย่อยที่มีขนาด เท่ากับ 4 และรอบที่ 3มีการจัดเรียงที่ ย่อยขนาดเท่ากับ 8 ซึ่งกลุ่มย่อยที่มีขนาด 8 จะมี 4 ค่าที่จัดเรียงเรียบร้อยแล้วแต่ในละกลุ่มจะมีกลุ่มย่อย 32 กลุ่ม การทำงานของการเรียงลำดับแบบเซลล์โดยเฉลี่ยจึงใช้เวลา o(m1แต่ยังถือว่าการทำงานยังใช้เวลาทรายยกกำลังสอง
การเรียงลำดับแบบผสาน
                            การจัดเรียงลำดับแบบต่างๆ ที่ได้ผ่านมา จะเห็นว่าเวลาที่ต้องใช้ในการจัดเรียงลำดับไม่เร็วกว่าหรืออยู่ในช่วงของ o(n2) สำหรับการจัดเรียงแบบที่จะกล่าวถึงใช้ o(n LOQ)  และเป็นเวลาที่จัดเรียงลำดับมีการเปรียบเทียบค่าที่ไม่สามารถทำงานได้ เร็วกว่านี้ ซึ่งการจัดเรียงลำดับมีอยู่หลายแบบ และ เป็นมาตรฐานโดยใช้เวลาที่ดีที่สุด ตารางที่ 11.0 อัลกอริทึมการเรียงลำดับแบบผสาน


1.  ถ้าค่าในกลุ่ม(Sequence) มีจำนวนมากกว่าหรือเท่ากับ 2 ให้ทำขั้นตอนที่ 2-5
2. ให้ am เป็นค่าที่อยู่ตรงกลางของค่าทั้งหมดในกลุ่ม
3. ทำการเรียงลำดับค่าที่อยู่ในกลุ่มย่อย (Sequence)   ที่มาก่อนหรือด้านซ้ายของค่า am  
4. ทำการเรียงลำดับค่าที่อยู่ในซึ่งเป็นค่าที่เหลือจากกลุ่มย่อยแรกคือ ด้านขวาของค่า am
5. ทำการผสานค่าจากทั้งห้องสมุดที่จัดเรียงลำดับเรียบร้อยแล้ว   

                 อัลกอริทึมทำได้ทีการมีการทำงานแบบรีเคอร์ชีฟ(Recuisiv) โดยในตอนที่ 3 และ 4 มีการเรียกตัวเองขึ้นมาทำงาน และมีอัลกอริทึมย่อยทำงานอย่างผสมผสาน ค่าจากสองกลุ่มย่อยโดยการเปรียบเทียบค่าที่ละคู่จากสองกลุ่มย่อย ดั้งในรูปที่ 11.9 และนำค่าที่น้อยกว่าไปเก็บไว้ยังกลุ่มที่ รับค่าเก็บไว้ต่อจากค่าก่อนหน้านี้ เมื่อทำหมดทั้งสองค่าทั้งสองกลุ่ม ก็จะได้ค่าทั้งหมดมีการจัดเรียงลำดับ

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                                                                

                     รูปที่ 11.9 วิธีการผสานได้เป็นตารางที่ 11.11 มีฟังก์ชันหลัก คือ merqeSort ที่ทำงานแบบ  บีเคอร์ชิฟ และฟังก์ชัน  merqe ใช้ผสานค่าให้เรียงตามลำดับ
ตารางที่ 11.11 ฟังก์ชันเรียงลำดับแบบผสาน


Void merge int key[], int lower,int middle int upper){
         Int i=lower;
         Int j=middle;
         Int k=0;
         Int *aTemp=malloc(sizeof(int)*(upper-lower) );
         If(key[middle-1]>key[middle]){
         While( (i<middle)&&(j<upper) ) {
         aTemp[k++]=key[i++];
         else
         aTemp[k++]= key[j++];
}
        While(i<middle)
         aTemp[k++]=key[i++];
        While(j<middle)
         aTemp[k++]= key[j++];
         i=0;
         while(i<k)
         key[lower++]=aTemp[i++];
}
Void mergeSort (int key[], int lower,int upper){
        If (upper-lower>=2){
        Int middle=(lower+upper){
        mergeSort(key,lower+midde);
        mereSort(key,middle,upper);
        merge(key,lower,middle,upper);
}

 

                        ฟังก์ชัน mereSort ทำการแบ่งอาร์เรย์เป็นอาร์เรย์ย่อย (Subarray) จนกว่าจะมีขนาดเล็กลงเหลือ 0 หรือ 1 จากนั้นนำแต่ละส่วนมาผสานกันรวมกันจนได้ขนาดเดียวกันกลับมาเท่าเดิม  ส่วนฟังก์ชันจะถูกเรียกให้ผสานค่าจากสองกลุ่ม ให้เรียงตามลำดับและต้องใช้อาร์เรย์ชั่วคราว (Temporaoy Array) เพื่อจะรวบรวมค่าที่จะการผสานกันและทำการคัดลอกกลับไปยังตำแหน่งเดิมของอาร์เรย์ย่อยตัวเดิม
                          ตัวอย่างการเรียงลำดับแบบผสานในดั้งรูป 11.10 โดยใช้อาร์เรย์ตัวเดิม ซึ่งจะถูกแบ่งครึ่งไปเรื่อยๆ จาก 1 อาร์เรย์ เป็น 2 อาร์เรย์ย่อย เป็น 4 อาร์เรย์ย่อย และเป็น 8 อาร์เรย์ย่อย เรียงลกดับค่า โดยเริ่มทำในส่วนด้านซ้ายจากนั้นจึงมาทำด้านขวาตามลำดับมาเลื่อยๆ จนมาถึงการผสานครั้งสุดท้ายก็จะได้เป็นอาร์เรย์ที่มีค่าทั้งหมดจัดเรียงตามลำดับ


66

33

99

55

88

22

44

77

 



88

22

44

77

66

33

99

55

 


99

55

44

77

66

33

88

22

                                                                                             


66

33

99

55

88

22

44

77

                                                      


22

88

44

77

                                                                            


33

66

55

99

                          
                                                     

33

55

66

99

22

44

77

88

                   


22

33

44

55

66

77

88

99

 

 

 

 

จากคัวอย่างเป็นกระบวนการแยกและรวมกัน โดยค่าที่จัดเรียงมีทั้งหมด 8 ค่า มีการแยกค่าออก 3 ระดับ การทำงานทั้งหมดมี 6 ระดับ และเป็นสองเท่า ของจำนวนเวลา n ที่ถูกการหารครึ่งจากการหารด้วย 2 เท่า ได้เป็นไนบรารี่ลอกการิทึม (Binary Loqarithm) ของ n Loq n การทำงานทั้งหมดมีจึงมี (2 Loq n) ระดับในการเรียงระดับค่า โดยแต่ระดับมีการเปรียบเทียบทุกค่า จึงเท่ากับ n ก็จะได้เปรียบเทียบค่าทั้งหมด
การเรียงลำดับแบบรวดเร็ว
การเรียงลำดับแบบรวดเร็วเป็นอัลกอริทึมอีกแบบที่ทำด้วยวิธีการแบ่งและยึดรวมกัน
(Divde-and-Conquer) และใช้รีเคอร์ชิฟ ซึ่งดรณีเฉลี่ยจะใช้เวลา O(n Loq n) คิดค้นโดย C.A.R. Hoare เช่นเดียวกับการเรียงลำดับแบบผสานที่การทำงานแบ่งเป็นส่วน จะแบ่งค่าในกลุ่มออกเป็นสองกลุ่มย่อยที่แยก ในการแบ่งส่วน ขั้นตอนที่สองเป็นการเรียงลำดับแต่ละกลุ่มย่อยที่ถูกแบ่งแบบเคอร์ชิฟ และอัลกอริทึมในการจัดเรียงลำดับแบบรวดเร็วได้เป็นดั้งในตารางที่ 11.12
ตารางที่ 11.12  อัลกอริทึมการเรียงลำดับแบบรวดเร็ว


1.ถ้าค่าในกลุ่มมีจำนวนมากกว่าหรือเท่ากับ 2 ให้ทำขั้นตอนที่ 2-4
2.ให้ค่าแรก  ap  เป็นแกนหลัก แบ่งส่วนในกลุ่มออกเป็น {ap,…aq…1} และได้เป็น 3 กลุ่มย่อย
3.ทำการเรียงลำดับค่าที่อยู่ในกลุ่มย่อย x
4.ทำการเรียงลำดับค่าที่อยู่ในกลุ่มย่อย y

             เมื่อเขียนเป็นฟังก์ชัน เรียงลำดับแบบรวดเร็วได้เป็นตารางที่ 11.13 มีฟังก์ชันหลัก คือ quickSort ที่ทำงานแบบรีเคอร์รีเคอร์ซิฟ  และมีฟังก์ชัน partition ใช้สำหรับแบ่งกลุ่มออกเป็นกลุ่มด้านขวาที่มีค่า
ตารางที่ 11.13 ฟังก์ชันเรียงลำดับแบบรวดเร็ว


Int partion(int key[] int lower int upper){
     Int pivot=key[lower];
     Int down=lower;
     Int up=upper;
While(down<up){
     While (key[down]<=pivot)&&(down<up){
     Down++;
     While (key [up]>pivot)
     Up--;
     If(down<up)
     Sawp(&key[down],&key[up]);
}
     Key[lower]=key[up];
     Key[up]=pivot;
     Return up;
}
    Void quickSort(int key[], int lower,int upper){
     If(upper-lower>=1){
     Int pivot=partition(key,lower,upper);
quickSort(key,lower,pivot-1);
quickSort(

ตัวอย่างการเรียงลำดับแบบรวดเร็วดั้งในรูปที่ 11.11 โดยใช้อาร์เรย์ตัวเดิม ซึ่งครั้งแรกจะทำการแบ่งครึ่งโดยกำหนดให้ค่าแรกซ้ายมือเป็นแกนหลัก ต่อจากนั้นอ่านค่าทางขวามือสุดถอยกลับลงมาเลื่อยๆจนสินสุดเมื่อพบค่าที่น้อยกว่าค่าที่น้อยกว่าค่าของแกนหลัก แล้วนำค่าทั้งสองสลับตำแหน่งกัน ทำเช่นนี้จนกระทั้งการอ่านขึ้นกับการอ่านลงมาพบกันก็ใช้ค่าของตำแหน่งนั้นสลับตำแหน่งกับค่าแกนหลัก และเป็นตำแหน่งที่ถูกต้อง ในการเรียงลำดับ เช่น ในครั้งแรกให้ค่า 66 เป็นแกนหลัก อ่าขึ้นไปจนหยุดค่าที่ 99 และอ่าลงมาอยู่ที่ 22 จึงสลับตำแหน่งกัน ทำต่อพบที่ค่า 88 กับ 55 จึงสลับตำแหน่งกัน สุดท้ายเมื่ออ่านขึ้นและอ่านลงมาพบกันจึง สลับตำแหน่งของค่า 55 กับ 66 ซึ่งเป็นแกนหลักและอยู่ในตำแหน่งที่ถูกต้อง จากนั้นทำส่วนที่ เหลือทั้งด้านซ้ายและด้านขวาแบบเดิมโดยการรีเคอร์ซีฟจนเหลือเพียงค่าเดียวในกลุ่มย่อยจึงจบการทำงาน

66

33

99

44

88

55

22

77

66

33

22

44

88

55

99

77

66

33

22

44

55

88

99

77

55

33

22

44

66

88

99

77

88

99

77

88

77

99

77

88

99

55

33

22

44

44

33

22

55

 

44

33

22

22

33

44

 

22

33

22

33

  

 

22

33

44

55

66

77

88

99

 

รูปที่ 11.11 ขั้นตอนการเรียงลำดับข้อมูลแบบรวดเร็ว

                   การเรียงลำดับแบบรวดเร็วคล้ายกับการเรียงลำดับแบบผสาน ทั้งสองแบบ ใช้วิธีการแบ่งและยึดรวมกันเป็นแบบรีเคอร์ชิฟ ดั้งนั้น เวลาที่ใช้ทำงานในกรณีเฉลี่ยจึงเท่ากับ o(n Loq n) อย่างไรก็ตามการเรียงลำดับแบบรวดเร็วมีความซับซ้อนมากว่า ในกรณีแย่สุด คือ การเรียง  ลำดับแบบรวดเร็วจะใช้เวลา (n2) เกิดขี้นทุกค่าในอาร์เรย์  มีการจัดเรียงลำดับก่อนแล้ว ทำให้การแบ่งส่วนแต่ละครั้ง ไม่มีการย้ายแกนของหลักจะอยู่ด้านซ้ายเสมอและได้กลุ่มย่อย ด้านขวาด้านที่  ลดขนาดเพียงค่าเดียว การทำงานจึงเป็น n-1 และมีการเปรียบเทียบค่าเท่ากับ o(n) จึงใช้เวลาเปรียบเทียบค่า o(n Loq n)
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

    
         
                          รูปที่ 11.12 ลักษณะการเรียงลำดับข้อมูลแบบรวดเร็วในกรณีดีที่สุด
                           จะเห็นว่าค่าของแกนหลักมีความสำคัญต่อประสิทธิภาพการทำงาน จึงต้องมีวิธีการเข้ามาช่วยในการเลือกค่าที่จะมาเป็นแกนหลัก เพื่อให้ค่าเก็บอยู่ไกล้ตำแหน่งตรงวกลางมากที่สุดรวดเร็วในกรณี เฉลี่ยเท่ากับ o(n  Loq n) ส่วนกรณีแย่ที่สุด จะใช้เวลา o(n2) แต่ก็ถือว่าเป็นแบบที่ใช้งาน ไม่ต้องใช้หน่วยความจำเพิ่มเติม การเรียงลำดับแบบฮีพ ที่ผ่านมาการจัดเรียงลำดับแบบผสานและแบบรวดเร็วใช้เวลาในการทำงานเท่ากับ o(n Loq n) ซึ่งดีกว่าการจัดเรียงลำดับที่ต้องใช้เวลา O(n2) ด้วยปรปะสิทธิ์ในการเปรียบเทียบ n ค่าที่ใช้เวลาเพียง o(n Loq n) แทนที่ต้องใช้เวลา o(n) อัลกอริทึม ทำงานโดยวิธีการแบ่งและยึดรวมกัน (Divide-and-Conquer) 

 

 

 

 

 

 

 

 

 

 

 

 


                                                                                

 

 

 

 

 

 

                                            รูปที่ 11.13 วิธีการจัดเรียงลำดับข้อมูลแบบฮีพ
แนวคิดของการเรียงลำดับแบบฮีพเหมือนกับการนเรียงลำดับแบบเลือก คือ เลือกค่าที่ มากที่สุดจากกลุ่มของค่าที่ยังเหลืออยู่ และยังไม่จัดเรียงลำดับ จากนั้นสลับตำแหน่งให้ถูกต้อง ซึ่งใช้เวลาการทำงานเท่ากับ n-1 เป็นเส้นตรงกับการเรียงลำดับแบบเลือก ที่ใช้เวลาเป็นอัลกอริทึม
ตารางที่ 11.14 อัลกอริทึมการเรียงลำดับแบบฮีพ          


1.สร้างฮีพเพื่อเก็บค่าในกลุ่ม (Sepuence)
2.ทำขั้นตอน 3-4ซ้ำตั้งแต่ i=n-1จนถึง i=1
3.สลัลตำแหน่งกับระหว่าง a กับ a
4.ทำการฮิฟปิฟาย

                   การเรียงลำดับแบบฮีพแบ่งการทำงานออกเป็น  2 ช่วง คือ ช่วยการสร้างฮีพ กับช่วง ปรับปรุงฮีพให้จัดเรียงใหม่  เมื่อเขียนเป็นฟังก์ชัน หลัก

ตารงที่ 11.15 ฟังก์ชันเรียงลำดับแบบฮีพ


Void heapify(int key[],int father, int size){
         Int tmp=key[father*2+1<size; father=child){
         Int child;
         For (;father*2+1<size; father=child){
         Child=father*2+1;
         If(child<size-1&& key[child+1]>[child] )
         Child++;
         If(key[child]>tmp
         Key[father]=key[child];
         Else
         Break;
}
         key[father]=tmp;
}
         void herapsort( int key[],int size){

         int I;
         for(i=size/2; i>=0;i--)
         heapify(key-1;I,size);
         or(i=size=1;i>0;i--){
         swap(&key[0],&key[i];
         heapiffy(key,o,.i);
         heapify(key,o,i);
}
}

 

ตัวอย่างการเรียงลำดับแบบฮีพจะใช้อาร์เรย์ที่ผ่านมา โดยเริ่มต้นเป็นการสร้างฮีพและจัดลำดับให้ถูกต้อง ดั้งในรูปที่ 11.14 ซึ่งแสดงในลักษณะที่เป็นเนบรารี่ทรีละอาร์เรย์ และการทำงานให้ฟังก์ชัน โดยเริ่มที่ โหนดตำแหน่งตรงกลาง คือ 4 เพื่อเปรียบเทียบค่าขิงโหนดพ่อ กับลูกมีค่ามากกว่า จะสลับตำแหน่งกัน และทำงานแบบเดิมทุก
โหนดถัดลงมาจนถึงโหนด 0 เช่น ในรอบที่ 4 หรืออาร์เรย์  4 หรืออาร์เรย์ 4 ไม่มีโหนดลูกจึงไม่มีการเปรียบเทียบ ในรอบที่ 5 เริ่มที่โหนด 0 หรืออาร์เรย์  0 เมื่อเปรียบเทียบกับโหนด 1 และ 2 พบว่าโหนด 2 มีค่ามากกว่าจึงสลับตำแหน่งกัน ต่อจากนั้นที่โหนด 2 เปรียบเทียบกับ โหนด 5 และ 6 พบว่าไม่มากกว่า จึงหยุดทำงาน และเป็นไปตามคุณสมบัติของฮีพที่โหนดพ่อมี ค่ามากกว่าโหนดลูก โดยโหนด 0 หรืออาร์เรย์  หรืออาร์เรย์ คือ 99

66

99

44

33


88

22

55

77

 

66

33

99

55

88

22

44

77

                                                                                 ฮีพ 1

 

 

 

 

 

 

66

99

44

33


88

22

77

55

 

66

33

99

77

88

22

44

55

                                                                                 ฮีพ 2


66

99

44

33


88

22

77

55

 

66

33

99

55

88

22

44

55

                                                                                 ฮีพ 3

 

66

99

44

88


33

22

77

55

 

66

88

99

77

33

22

44

55

                                                                                 ฮีพ 4

 

99

66

44

88


33

22

77

55

 

99

88

66

77

33

22

44

55

                                                                                 ฮีพ 5

รูปที่ 11.14 การสร้างฮีพและจัดลำดับข้อมูลตามคุณสมบัติของฮีพ
   หลังจากสร้างฮีพจะเป็นการนำค่าที่มากที่สุดสี่โหนด 0 สลับตำแหน่งกับโหนดสุดท้ายก็ได้ค่ามากที่สุดอยู่ในตำแหน่งที่ถูกต้อง จากนั้นทำแบบเดิมกับค่าที่เหลือตั้งแต่ n-1 โหนดจนเหลือโหนดเดียวพร้อมกับปรับปรุงฮีพให้เป็นไปตามคุณสมบัติและการปรับปรุงเริ่มที่โหนด 0 ทุกครั้ง ดั้งในรูปที่ 11.14 เช่นหลังจากสลับตำแหน่งครั้งแรกระหว่างโหนด 7 และมาเกี่ยวข้องอีก จากนั้นปรับปรุงฮีพครั้งแรกจะมีการย้ายค่า ระหว่างโหนด 0.1และ 3 ค่าที่มีมากกว่าจะถูกย้ายไปอยู่ด้านบน คือ 88ส่วนค่าน้อยกว่าจะถูกย้ายลงมาล่างคือ 55 เมื่อสลับตำแหน่งครั้งที่ 2 ส่วนค่าน้อยกว่าจะถูกว่าไว้ด้านล่าง คือ 44 ทำแบบเดิมใจนถึงการสลับตำแหน่งครั้งที่ 7 และปรับปรุงฮีพ ครั้งที่ 7ที่เหลือเพียงโหนดค่าเดียวจึงจบการทำงาน

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

                การจัดเรียงลำดับที่ผ่านมาเป็นการเปรียบเทียบค่าที่ใช้เวลาทำงาน 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

 

การเรียงลำดับแบบเรดิกซ์
                เป็นแบบสุดท้ายของการเรียงลำดับภายในที่กล่าวถึงและไม่มีการเปรียบเทียบค่า เวลาที่ใช้ทำงานเป็น 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 ถัง ทำให้ใช้พื้นที่หน่วยความจำมากขึ้นด้วย

การเรียงลำดับและผสานแฟ้มข้อมูล

                การเรียงลำดับแบ่งออกเป็นการจัดเรียงภายในดังที่ได้กล่าวผ่านมาเป็นการจัดเรียงภายในหน่วยความจำหลัก และการจัดเรียงภายนอกซึ่งกล่าวถึงในที่นี้เป็นการจัดเรียงที่ใช้หน่วยความจำสำรองเพื่อจัดเรียงลำดับแฟ้มข้อมูลแบบลำดับ (Sequential File) แฟ้มรายงาน และนำไปใช้ในการปรับปรุงแฟ้มข้อมูล เพื่อพิจารณาจากแฟ้มข้อมูลมี 2,000 เรคคอร์ด เพื่อทำการจัดเรียงลำดับและมีเพียง 1,000 เรคคอร์ดที่สามารถใช้งานในหน่วยความจำแต่ละช่วงเวลา จึงไม่สามารถจัดเรียงลำดับพร้อมกันหมด แนวทางการแก้ปัญหาโดยใช้การจัดเรียงลำดับภายในทำการเรียงลำดับ 2 รายการย่อย (Sublist) ที่คัดลอกมาจากแฟ้มข้อมูล คือ เรคคอร์ด 1-1,000 กับ 1,000-2,000 ผลที่ได้คือ แฟ้มข้อมูลที่เก็บรายการย่อย 2 แฟ้ม และนำมาผสาน (Merge) รวมเป็นแฟ้มเดียวที่จัดเรียงลำดับเรคคอร์ดทั้งหมด ดังในรูปที่ 11.19 การผสานจะทำการเปรียบเทียบระหว่างค่าของคีย์ใน 2 รายการย่อย ถ้าค่าใดน้อยกว่าก็เขียนเก็บไว้ในแฟ้มข้อมูลผสาน (Merge File)

รายการย่อย 1
(เรคคอร์ด 1-1000)
กล่องข้อความ: ผสาน

                                  รายการผสาน
(เรคคอร์ด 1-2000)                                                                      รายการย่อย 1
(เรคคอร์ด 1-1000)

รูปที่ 11.19  การผสานรายการย่อยได้เป็นแฟ้มข้อมูลที่มีการจัดเรียงลำดับข้อมูล

 

                ตรรกะพื้นฐานการผสานจะมี key , key2 และ keyM ใช้อ้างถึงค่าของคีย์ในรายการย่อย 1  รายการย่อย 2  ที่เป็นแฟ้มอินพุต และแฟ้มข้อมูลผสานที่เป็นแฟ้มเอ้าท์พุตตามลำดับรายการย่อยจะถูกจัดเรียงลำดับตามค่าของคีย์เพื่อใช้ในการผสานและอาจมีความยาวไม่เท่ากัน เมื่อรายการย่อยใดถึงจุดสิ้นสุดแฟ้ม รายการย่อยอื่นที่ยังมีเรคคอร์ดเหลืออยู่ที่จะถูก

 

 

                                   ตารางที่ 11.20  อัลกอริทึมการผสานแฟ้มข้อมูล
 


  1. เปิดแฟ้มข้อมูล File1 กับ File2  เป็นแฟ้มอินพุต และเปิดแฟ้มข้อมูล File3 เป็นแฟ้มเอ้าท์พุต
  2. ให้ตัวแปร X อ่านค่าแรกในแฟ้มข้อมูล File1 และตัวแปร Y อ่านค่าแรกในแฟ้มข้อมูล File2
  3. ทำซ้ำแบบเดิมจนกว่าถึงท้ายแฟ้มข้อมูล File1 หรือ File2
    1. ถ้าค่า X-Y ให้ทำ

a.1  เขียนค่า X เก็บไว้ที่แฟ้มข้อมูล File3
a.2  ให้ตัวแปร X อ่านค่าตัวถัดไปในแฟ้มข้อมูล File1
                ไม่เช่นนั้น
                        b.1  เขียนค่า Y เก็บไว้ที่แฟ้มข้อมูล File3
                        b.2  ให้ตัวแปร Y อ่านค่าตัวถัดไปในแฟ้มข้อมูล File2

  1. ถ้าพบท้ายแฟ้มข้อมูล File1 คัดลอกค่าที่เหลือทั้งหมดจากแฟ้มข้อมูล File2 ให้กับแฟ้มข้อมูล File3 แต่ถ้าพบท้ายแฟ้มข้อมูล File2 คัดลอกค่าที่เหลือทั้งหมดจากแฟ้มข้อมูล File1 ให้กับแฟ้มข้อมูล File3

การจัดเรียงลำดับและผสานแฟ้มข้อมูลแบ่งออกเป็น 3 ขั้นตอน คือ

  1. ขั้นตอนการจัดเรียงลำดับภายใน เป็นการจัดเรียงลำดับค่าของเรคคอร์ดที่เก็บไว้ในแต่ละแฟ้มอินพุตที่ถูกแบ่งออกเป็นกลุ่มและมีจำนวนเรคคอร์ดเท่ากับเรียกว่ารัน (Run) ซึ่งจะกระจายรันเหล่านี้เก็บไว้ในแฟ้มอินพุตบนอุปกรณ์จัดเก็บข้อมูลตั้งแต่สองตัวขึ้นไป เช่น เทปแม่เหล็กหรือฮาร์ดดิสก์
  2. ขั้นตอนการผสาน เป็นการรวมค่าที่อยู่ในแต่ละรันจากหลายๆ แฟ้มอินพุตให้จัดเรียงตามลำดับ และนำมารวมไว้ด้วยกันได้เป็นหนึ่งรันในแฟ้มเอาท์พุตสำหรับใช้งานในรอบ (Phase) ถัดไป
  3. ขั้นตอนผลลัพธ์ที่ได้  เป็นการคัดลอกแฟ้มข้อมูลที่จัดเรียงลำดับเสร็จแล้วเก็บไว้บนสื่อจัดเก็บข้อมูลตามที่ต้องการ

โดยทั่วไป การนำอัลกอลิทึมมาใช้สำหรับขั้นตอนการจัดเรียงลำดับภายในคือการจัดเรียงแบบทัวร์นาเม้นต์ (Tourmament Sort) เนื่องจากใช้กับรันที่มีความยาวมากกว่าหน่วยความจำหลักที่ไม่สามารถเก็บได้หมด สำหรับเทคนิคการจัดเรียงลำดับแฟ้มข้อมูลหรือการจัดเรียงลำดับภายนอกเกือบทั้งหมดใช้วิธีตามขั้นตอนดังกล่าว จึงเรียกว่า การจัดเรียงลำดับและผสาน (Sort/Merges) และมีขั้นตอนการผสานหลายวิธีในการจัดเรียงลำดับและผสาน
ในการผสานแฟ้มข้อมูลที่เป็นอินพุตเข้ามา 2 แฟ้มในแต่ละครั้งเรียกว่าการผสาน2-ทาง (2-way Merge) ดังนั้น ถ้ามีแฟ้มอินพุต M แฟ้มจะเรียกว่าการผสาน M-ทาง (M-way Merge) โดยการผสานธรรมดา M-ทาง (M-way Merge) จะเป็นการผสานที่มีแฟ้มอินพุต M แฟ้มกับแฟ้มเอ้าท์พุตเพียง 1 แฟ้ม มีลักษณะเช่นเดียวกับการเรียงลำดับ แบบผสานที่ผ่านมาแทนที่ใช้อาร์เรย์เก็บค่าแต่จะใช้แฟ้มข้อมูลเก็บค่าแทน แต่การผสานธรรมดา ต้องใช้การทำงานของ I/O เกือบครึ่งหนึ่งของทั้งหมดในการกระจายรันที่ได้จากการผสานในแต่ละรอบให้กับหลายแฟ้มข้อมูลเพื่อเตรียมเป็นแฟ้มอินพุตในรอบถัดไป ความต้องการคัดลอกข้อมูลกลับไปกลับมา โดยกระจายผลลัพธ์ที่ได้จากการผสานส่งตรงไปให้แฟ้มข้อมูลที่จะเป็นแฟ้มอินพุตในรอบถัดไป ดังนั้น การผสานสมดุล M-ทางจะใช้ 2M แฟ้ม ในลักษณะการย้ายข้อมูลกลับไปกลับมาระหว่างแฟ้มอินพุตและเอ้าท์พุตที่มีจำนวนเท่ากัน

ตัวอย่างการเรียงลำดับและผสานสมดุล
                ตัวอย่างที่นำมาใช้จัดเรียงลำดับภายนอกจะใช้แฟ้มข้อมูลที่สมมุติให้มี 36 เรคคอร์ด โดยนำเฉพาะค่าของคีย์มาใช้แสดงและใช้วิธีการผสานสมดุล 2-ทาง โดยมีการจัดเรียงลำดับภายในได้ 3 เรคคอร์ดต่อหนึ่งรัน ดังนั้น ในการเรียงลำดับและผสานสมดุลจึงใช้เครื่องอ่านเทป 4 ตัว ซึ่งมีเทป 2 ม้วนเป็นแฟ้มอินพุตและอีก 2 ม้วนเป็นแฟ้มเอ้าท์พุต มีขั้นตอน ดังต่อไปนี้
                1. ขั้นตอนการเรียงลำดับภายในเป็นการเรียงลำดับค่าในเทป 1 เก็บไว้ในแต่ละวันแบ่งเป็น 12 วัน ๆ ละ 3 เรคคอร์ดและกระจายเก็บไว้ในแฟ้มอินพุตคือเทป3, 4 สลับกันไป
 

 


                2.  ขั้นตอนการผสานรอบที่ 1  โดยนำค่าในแต่ละรันจากแฟ้มอินพุต คือ เทป 3, 4 มาผสานรวมกันทีละคู่เก็บลงในแฟ้มเอ้าท์พุตคือ เทป 1, 2 สลับกัน จากเดิมที่มี 12 รันจะเหลือ 6 รัน ได้เป็นดังนี้

 

                3.  ขั้นตอนการผสานรอบที่ 2  โดยนำค่าในแต่ละรันจากแฟ้มอินพุต คือ เทป 1, 2 มาผสานรวมกันทีละคู่เก็บลงในแฟ้มเอ้าท์พุต คือ เทป 3, 4 สลับกัน จากเดิมที่มี 6 รันจะเหลือ 3 รัน ได้เป็น ดังนี้

 


                4.  ขั้นตอนการผสานรอบที่ 3 โดยนำค่าในแต่ละรันจากแฟ้มอินพุต คือ เทป 3, 4 มาผสานรวมกัน ซึ่งมีคู่เดียวเก็บลงในแฟ้มเอ้าท์พุต คือ เทป 1 จากเดิมที่มี 3 รันจะเหลือ 2 รัน โดยในเทป 1 มี 1 รัน และเทป 3 มี 1 รันที่ยังไม่ถูกผสาน ซึ่งเทป 2 ไม่ถูกนำมาใช้งาน ได้เป็นดังนี้
 

 


                5.  ขั้นตอนการผสานรอบที่ 4 โดยนำค่าในแต่ละรันจากแฟ้มอินพุต คือ เทป 1, 3 มาผสานรวมกัน ซึ่งมีคู่เดียวเก็บลงในแฟ้มเอ้าท์พุต คือ เทป 4 จากเดิมที่มี 2 รันจะเหลือ 1 รัน โดยในเทป 1 มี 1 รัน เรียงตามลำดับค่าทั้งหมด โดยเทป 2 ยังคงไม่ถูกนำมาใช้งาน ได้เป็นดังนี้
 

 


                ในการผสานแต่ละรอบรันทั้งหมดจะถูกหารด้วยจำนวนแฟ้มอินพุตในการผสาน ทำให้แต่ละรันมีความยาวเป็นเท่าของจำนวนแฟ้มอินพุตและจำนวนรันน้อยลงครึ่งหนึ่งของรัน ในเทปอินพุต ดังนั้น การผสานสมดุล M-ทาง ต้องใช้จำนวนรอบในการผสานเท่ากับ O([logM R/L]) เมื่อ R คือ จำนวนเรคคอร์ดและ L คือ ความยาวของรันในตอนเริ่มต้น เช่น ในตัวอย่างจำนวนรอบเท่ากับ élog2 36/3ù = 4 ถ้าให้ M หรือจำนวนแฟ้มอินพุตเท่ากับ 3 จะใช้จำนวนรอบเพียง élog3 36/3ù = 3 รอบ

                แต่เนื่องจากการทำงานของการผสานสมดุลทำให้แฟ้มเอ้าท์พุตบางแฟ้มอยู่เฉยๆ ไม่ถูกใช้งาน (เทป 2)  และเพื่อลดาจำนวนการคัดลอกค่าระหว่างแฟ้มอินพุตกับแฟ้มเอ้าท์พุต จึงใช้การผสานที่มี
มากกว่า M คือ ให้การอ่านแฟ้มข้อมูลมีมากกว่า M แฟ้มในช่วงเวลาหนึ่งก็จะได้ 2M-1 แฟ้มอินพุตและ 1 แฟ้มเอ้าท์พุต หรือนำแฟ้มเอ้าท์พุตของการผสานสมดุลที่ไม่ได้ใช้งานในการใช้มาเป็นแฟ้มอินพุตแทน ซึ่งได้เป็นการผสานไม่สมดุล (Unbalanced Merge) เกิดประโยชน์สูงสุดในการใช้แฟ้มข้อมูล โดยรูปแบบหนึ่งของการผสานไม่สมดุลที่นำมาใช้ คือ การผสานหลายขั้นตอน (Polyphone Merge) ซึ่งใช้แฟ้มอินพุตจำนวนคงที่ และการผสานหลายเฟส M-ทาง ก็จะใช้ 2M – 1 แฟ้มอินพุต

 

ตัวอย่างการเรียงลำดับและผสานหลายขั้นตอน
                สำหรับตัวอย่างนี้เป็นการผสานหลายขั้นตอน 2 – ทาง จึงใช้เทป 3 ม้วนเป็นแฟ้มอินพุตและ 1 ม้วนเป็นแฟ้มเอ้าท์พุตในแต่ละรอบ โดยสมมุติให้แฟ้มข้อมูลมี 34 เรคคอร์ดและการจัดเรียงลำดับภายในได้ 2 เรคคอร์ดต่อหนึ่งรัน ก็จะได้ทั้งหมด 17 รันและกระจายไปยัง 3 แฟ้มอินพุต โดยแฟ้ม 1 ได้ 7 วัน แฟ้ม 2 ได้ 6 รัน แฟ้ม 3 ได้ 4 รัน ซึ่งวิธีการกระจายรันดังในรูปที่ 11.20

รูปที่ 11.20  วิธีการกระจายรันไปให้พร้อมอินพุตในการผสานหลายขั้นตอน

                1. ขั้นตอนการเรียงลำดับภายในเป็นการเรียงลำดับค่าในเทป 1 เก็บไว้ในแต่ละวันแบ่งเป็น 17 รันๆ ละ 2 เรคคอร์ดและกระจายรันตามวิธีที่กล่าวมาเก็บไว้ในแฟ้มอินพุต คือ เทป 2 ได้ 7 รัน เทป 3 ได้ 6 รัน และเทป 4 ได้ 4 วัน และเทป 4 ได้ 4 รัน ได้เป็น ดังนี้

 

 


                2.  ขั้นตอนการผสานรอบที่ 1  โดยนำค่าในแต่ละรันจากแฟ้มอินพุต คือ เทป 2, 3, 4 มาผสานรวมกัน (การผสานที่มีแฟ้มอินพุตมากกว่า 2 ม้วน ในการรัดเรียงลำดับโดยใช้การเปรียบเทียบค่ากันอาจไม่เหมาะสม จึงเปล่ามาใช้คิวลำดับความสำคัญแทน และให้ค่าที่น้อยกว่ามีความสำคัญมากกว่า) และเก็บลงในแฟ้มเอ้าท์พุต คือ เทป 1 โดยเทป 2 เหลือ 3 รันและเทป 3 เหลือ 2 รัน จากเดิมที่มี 17 รันจะเหลือ 9 รันได้เป็นดังนี้

 

 


                3.  ขั้นตอนการผสานรอบที่ 2  โดยนำค่าในแต่ละรันจากแฟ้มอินพุต คือ เทป 1, 2, 3  มาผสานรวมกันและเก็บลงในแฟ้มเอ้าท์พุต คือ เทป 4 โดยเทป 1 เหลือ 2 รันและเทป 2 เหลือ 1 รัน จากเดิมที่มี 9 รันจะเหลือ 5 รันได้เป็นดังนี้

 

 

                4.  ขั้นตอนการผสานรอบที่ 3 โดยนำค่าในแต่ละรันจากแฟ้มอินพุต คือ เทป 1, 2, 4  มาผสานรวมกันและเก็บลงในแฟ้มเอ้าท์พุต คือ เทป 3 โดยเทป 1, 3, 4 เหลือม้วนละ  1 รัน จากเดิมที่มี 5 รันจะเหลือ 3 รันได้เป็นดังนี้
 

 


                5. ขั้นตอนการผสานรอบที่ 4 โดยนำค่าในแต่ละรันจากแฟ้มอินพุต คือ เทป 1, 3, 4 มาผสานรวมกันและเก็บลงในแฟ้มเอ้าท์พุต คือ เทป 2  จากเดิมที่มี 3 รันจะเหลือ 1 รันที่เรียงตามลำดับค่าทั้งหมด ได้เป็นดังนี้
 

 


                ในแต่ละรอบของการผสาน รันที่อยู่ในแฟ้มอินพุตจะถูกผสานเก็บไว้ที่แฟ้มเอ้าท์พุตจนกระทั่งมีแฟ้มอินพุตว่างหนึ่งแฟ้มซึ่งจะเป็นแฟ้มเอ้าพุตในรอบถัดไป ขณะที่แฟ้มอินพุตอื่นยังคงมีรันอยู่ แนวทางนี้จะช่วยลดการคัดลอกเรคคอร์ดเนื่องจากรอบถัดไปยังคงใช้แฟ้มอินพุตเดิมที่มีรันเหลืออยู่

 

เริ่มรอบ 1

จบรอบ 1

จบรอบ 2

จบรอบ 2

จบรอบ 3

 

วันเริ่มต้น

เทป 2+3+4

เทป 1+2+3

เทป 1+2+4

เทป 1+3+4

เทป 1

0

4

2

1

0

เทป 2

7

3

1

0

1

เทป 3

6

2

0

1

0

เทป 4

4

0

2

1

0

รวม

17

9

5

3

1

                จากตัวอย่างมีลักษณะของขั้นตอนการผสานรวมกันในช่วงการผสานแต่ละรอบดังในรูปที่ 11.21 แสดงให้เห็นถึงลำดับการกระจายรันในช่วงขั้นตอนการจัดเรียงลำดับภายในให้กับแฟ้มอินพุต ซึ่งผลรวมที่ได้ในรูปที่ 11.21 อยู่ในรูปแบบของตัวเลข Fibonacci และเป็นวิธีที่ดีที่สุดเพื่อใช้ในการกระจายรัน

 

 

 

 

นายธีระทัศน์ เสียงอ่อน
5039011012