วันอาทิตย์ที่ 23 เมษายน พ.ศ. 2560

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

บทที่ 8 
การเรียงลำดับข้อมูล 
( Sorting )

                  หนึ่งในการดำเนินงานที่มีการใช้กันมากในคอมพิวเตอร์ก็คือ  การเรียงลำดับข้อมูล 
(Sorting)  เพราะการเรียงลำดับข้อมูลนั้นมีการนำไปใช้งานบ่อยมาก  โดยเฉพาะการประมวลผล
ข้อมูลด้วยคอมพิวเตอร์    เช่น   การเรียงลำดับข้อมูลนักศึกษาตามคณะและสาขา  การเรียงลำดับ
ข้อมูลพนักงานตามเลขรหัส  และการจัดเรียงรายชื่อสมุดโทรศัพท์  เป็นต้น ซึ่งการเรียงลำดับข้อมูล
นอกจากจะทำให้ข้อมูลถูกจัดให้มีระเบียบแล้ว  ยังทำให้การค้นหาข้อมูลมีความรวดเร็วขึ้นอีกด้วย
 8.1 ประเภทการเรียงลำดับข้อมูล (Sort  Classifications)
การเรียงลำดับข้อมูลยังสามารถแบ่งออกเป็น 2 ประเภทด้วยกันคือ
1. การเรียงลำดับข้อมูลแบบภายใน (Internal  Sorting)
                     ใช้  Primary Memory หรือ RAM ในการเรียงลำดับข้อมูล โดยการเรียงลำดับ
ข้อมูลวิธีนี้ จะเอาข้อมูลทั้งหมดที่ต้องการเรียงมาเก็บไว้ใน RAMแล้วเรียงลำดับที่เดียวทั้งหมด

ข้อดี        - RAM ทำงานได้เร็ว
ข้อเสีย     - RAM มีความจุน้อย
             - เมื่อปิดเครื่องข้อมูลที่เรียงลำดับไว้จะหายไป

2. การเรียงลำดับข้อมูลแบบภายนอก  (External  Sorting)
                ใช้ Secondary Storage เช่น Hard disk  จะในกรณีที่ข้อมูลมีปริมาณมาก การ
จัดเรียงข้อมูลจะมีการแบ่งข้อมูลออกเป็นส่วนๆ  เพื่อดึงข้อมูลมาเรียงลำดับใน RAM ที่ละส่วน
  
ข้อดี        -  มีความจุสูง
              -  เมื่อปิดเครื่องข้อมูลที่เรียงลำดับไว้ยังอยู่
ข้อเสีย      -  ทำงานช้า
ลำดับการจัดเรียง  (Sort  Order)
                   ข้อมูลสามารถที่จะทำการจัดเรียงจากน้อยไปหามาก  (Ascending)หรือเรียง
ลำดับจากมากไปหาน้อย (Descending) ก็ได้  ซึ่งลำดับการเรียงจะขึ้นอยู่กับคุณสมบัติของข้อ
มูลที่จะนำไปจัดเรียง  ตัวอย่างข้อมูลที่เหมาะสมกับการจัดเรียงจากน้อยไปหามาก  เช่น  สมุด
โทรศัพท์  พจนานุกรม  สำหรับตัวอย่างข้อมูลที่เหมาะสมกับการจัดเรียงจากมากไปหาน้อย  เช่น
เกรดเฉลี่ยสะสมของนักศึกษา หรือคะแนนของผู้เล่นเกม ซึ่งมักเป็นสถิติจากลำดับสูงลงมาต่ำ
เป็นต้น
ความคงที่ในการเรียงลำดับข้อมูล (Sort  Stability)
                         ความคงที่ในการเรียงลำดับข้อมูล  ถือเป็นคุณสมบัติหนึ่งของการเรียงลำดับข้อ
มูล โดยเฉพาะข้อมูลที่มีคีย์ซ้ำกัน  โดยเมื่อมีการอินพุตกลุ่มข้อมูลที่มีคีย์ซ้ำกันเข้ามาจัดเรียงลำ
ดับและแสดงผลออกเป็นเอาต์พุตคุณสมบัติของความคงที่ก็คือ กลุ่มคีย์ซ้ำกันนั้นควรมีลำดับข้อมูล
เหมือนกับข้อมูลชุดเดิม  ให้พิจารณาจากรูปที่ 8.2 (a) ซึ่งเป็นข้อมูลที่อินพุตเข้ามาโดยยังไม่ได้
ผ่านการจัดเรียงให้สังเกตดี ๆว่าจะมีข้อมูลอยู่ 3เรคอร์ดด้วยกันที่มีคีย์ซ้ำกัน  ซึ่งก็คือหมายเลข
212 โดยหลังจากที่นำข้อมูลเหล่านี้มาผ่านการจัดเรียงด้วยอัลกอริทึมการเรียงลำดับข้อมูลแล้ว
จะเห็นได้ว่าเอาต์พุตจากรูปที่ 8.2 (b) และรูปที่ 8.2 ( c ) นั้น  ลำดับข้อมูลของกลุ่มคีย์ 212
นั้นไม่เหมือนกัน  โดยจากรูปที่ 8.2 (b) นั้นถือว่าเป็นการเรียงลำดับข้อมูลที่มีความคงที่ เนื่อง
จากกลุ่มคีย์  212ยังคงซึ่งลำดับเดิมเหมือนกับข้อมูลต้นฉบับคือ green, yellow และ blue
ในขณะที่รูปที่ 8.2 ( c  )นั้นมีความคลาดเคลื่อน  เนื่องจากตำแหน่งของ  blue ได้คลาดเคลื่อนไป
โดยถูกจัดไว้ในลำดับแรกภายในกลุ่ม  ซึ่งถือว่าไม่มีความคงที่ในการเรียงลำดับข้อมูล

8.2 ประสิทธิภาพของการเรียงลำดับข้อมูล  (Sort  Efficiency)
                               ประสิทธิภาพของการเรียงลำดับข้อมูล  คือการวัดผลประสิทธิภาพเชิงสัมพันธ์
ของการเรียงลำดับซึ่งโดยปกติแล้ว  ได้มีการประมาณค่าจากการเปรียบเทียบ   และการเคลื่อนย้าย
ลำดับเพื่อจัดเรียงภายในลิสต์ที่ไม่ได้เรียงลำดับข้อมูลไว้  โดยในที่นี้จะกล่าวถึงการวัดประสิทธิภาพ
ของการเรียงลำดับข้อมูลแบบภายในเท่านั้นซึ่งประสิทธิภาพของการเรียงลำดับข้อมูลของแต่ละอัล
กอริทึมจะใช้แทนสัญลักษณ์บิ๊กโอ เช่น  ประสิทธิภาพการจัดเรียงข้อมูล  O(n)  ย่อมดีกว่า O(n2)
เป็นต้น
 8.3 วิธีการเรียงลำดับข้อมูล
                  เนื้อหาต่อไปนี้จะแสดงวิธีการเรียงลำดับข้อมูลด้วยวิธีต่างๆ ซึ่งจะกล่าวถึงราย
ละเอียดเกี่ยวกับขั้นตอนของการจัดเรียงข้อมูล  อัลกอริทึมการจัดเรียงข้อมูลรวมถึง
ประสิทธิภาพของวิธีการเรียงลำดับข้อมูลในแต่ละวิธีโดยในที่นี้จะขอกล่าวถึงการเรียงลำดับ
ข้อมูลด้วย

วิธีต่อไปนี้
1.  การเรียงลำดับข้อมูลแบบ   Selection  Sort
2.  การเรียงลำดับข้อมูลแบบ   Heap  Sort
3.  การเรียงลำดับข้อมูลแบบ   Insertion  Sort
4.  การเรียงลำดับข้อมูลแบบ   Bubble   Sort
5.  การเรียงลำดับข้อมูลแบบ   Quick   Sort
6.  การเรียงลำดับข้อมูลแบบ   Merge   Sort
  1. การเรียงลำดับข้อมูลแบบ  Selection  Sort
                    การเรียงลำดับข้อมูลแบบ Selection  Sort  หรือการเรียงลำดับข้อมูลแบบ
เลือกถือว่าเป็นวิธีการเรียงลำดับข้อมูลที่เรียบง่าย  ตรงไปตรงมาวิธีหนึ่ง  จนสามารถกล่าว
ได้ว่า  Selection Sort  นี้จัดเป็นวิธีหนึ่งที่มีอยู่ในสัญชาตญาณโดยธรรมชาติของมนุษย์
เพื่อใช้กับการเรียงลำดับข้อมูลก็ว่าได้การทำงานในแต่ละรอบของวิธีนี้  จะทำการค้นหาหรือ
สแกนค้นหาตั้งแต่ตัวแรกจนถึงตัวสุดท้าย  หลังจากที่ได้พบตำแหน่งของค่าที่น้อยที่สุดแล้ว
ก็จะทำการสลับตำแหน่งกัน  จากนั้นในรอบต่อไป  ก็จะขยับตำแหน่งไปยังตัวถัดไป  ซึ่งก็คือ
ตัวที่สอง  และทำการสแกนข้อมูลที่มีค่าน้อยที่สุดตั้งแต่ตัวที่สองไปจนถึงตัวสุดท้าย  เมื่อพบ
แล้วก็จะสลับตำแหน่งกันเช่นเคย  โดยจะทำเช่นนี้ไปเรื่อย ๆ จนครบทุกตัว  ก็จะได้ชุดข้อมูล
ที่จัดเรียงเรียบร้อยสมบูรณ์
รอบที่ 1 :
              เริ่มต้นจากข้อมูลต้นฉบับ  ซึ่งเป็นชุดตัวเลขที่ยังไม่ผ่านการจัดเรียงทั้งหมด
โดยให้ทำการค้นหาค่าที่น้อยที่สุดจากช่องที่ 1 ไปจนถึงช่องที่ 6 ผลที่ได้คือเลข 8 หลังจาก
นั้นให้ทำการสลับตำแหน่งกับ 23และในส่วนของกำแพงก็จะเลื่อนขยับเข้าไปหนึ่งตำแหน่ง
                รอบที่ 2 :
                เริ่มต้นค้นหาจากช่องที่ 2 คือตัวเลข 78 ไปจนถึงช่องที่ 6 พบค่าน้อยที่สุดคือ
23 ให้ทำการสลับตำแหน่งระหว่างตัวเลข 78 กับ 23 และในส่วนของกำแพงก็จะเลื่อนขยับ
เข้าไปหนึ่งตำแหน่ง
                รอบที่ 3 :
                เริ่มต้นค้นหาจากช่องที่ 3 คือตัวเลข 45 ไปจนถึงช่องที่ 6 พบค่าน้อยที่สุดคือ
32 ให้ทำการสลับตำแหน่งระหว่างตัวเลข 45 กับ 32 และในส่วนของกำแพงก็จะเลื่อนขยับ
เข้าไปหนึ่งตำแหน่ง
                รอบที่ 4:
                เริ่มต้นค้นหาจากช่องที่ 4 คือตัวเลข 78 ไปจนถึงช่องที่ 6 พบค่าน้อยที่สุดคือ
45 ให้ทำการสลับตำแหน่งระหว่างตัวเลข 78 กับ 45 และในส่วนของกำแพงก็จะเลื่อนขยับ
เข้าไปหนึ่งตำแหน่ง
                รอบที่ 5:
                สำหรับรอบนี้จัดเป็นรอบสุดท้าย  เนื่องจากภายในลิสต์เหลือเพียงข้อมูลสอง
ตัวสุดท้ายคือ 78และ 56 ปรากฏว่าค่า 56 น้อยกว่า  จึงทำการสลับตำแหน่งกัน หลังจากนั้น
ก็คงเหลือไว้แต่เพียงข้อมูลที่ได้จัดเรียงไว้อย่างสมบูรณ์
   
2. การเรียงลำดับข้อมูลแบบ  Heap  Sort
                   เราได้ศึกษาเกี่ยวกับฮีพทรีมาแล้ว  โดยโครงสร้างของฮีพทรีนั้น  รูทโหนดหรือ
โหนดพ่อจะมีค่ามากกว่าสมาชิกในทรีในกรณี  Max-Heap  หรือน้อยที่สุดกว่าสมาชิกในทรี
ในกรณี Min-Heap ดังนั้นในที่นี้จึงขอทบทวนเล็กน้อยด้วยการพิจารณารูปที่ 8.4  ที่แสดง
ถึงฮีพทรี  และการแทนฮีพทรีลงในหน่วยความจำอาร์เรย์
3. การเรียงลำดับข้อมูลแบบ  Insertion  Sort
                  การเรียงลำดับข้อมูลแบบ Insertion  Sort  หรือการเรียงลำดับข้อมูลแบบ
แทรกจัดเป็นวิธีการเรียงลำดับข้อมูลที่ไม่ซับซ้อนเช่นกัน  วิธีนี้เป็นพื้นฐานทางเทคนิคที่นำ
ไปใช้กับการเรียงไพ่ด้วยมือ โดยผู้เล่นจะทำการจัดเรียงไพ่ด้วยการดึงไพ่ที่ต้องการออกมา
แทรกในตำแหน่งที่เหมาะสมในช่วงลำดับการเรียงในขณะนั้น  โดยพิจารณาจากรูปที่ 8.7 
ซึ่งเป็นภาพแสดงหลักการเรียงลำดับข้อมูลแบบ Insertion  Sort
                     รูปที่ 8.7  หลักการเรียงลำดับข้อมูลแบบ  Insertion  Sort
                  ขั้นตอนการทำงานของการเรียงลำดับข้อมูลแบบ Insertion  Sort  นั้น ได้นำ
เทคนิคของการจัดเรียงแบบ  Insertion  มาปรับปรุง  กล่าวคือแทนที่จะอ่านหรือสแกนข้อ
มูลจนครบทุกตัวเพื่อหาค่าที่น้อยที่สุด  ก็จะทำการเปรียบเทียบค่ากับตำแหน่งถัดไปแทน
โดยถ้าตำแหน่งถัดไปนั้นมีค่าน้อยกว่า ก็จะนำมาสลับตำแหน่งกันด้วยการนำมาแทรกในตำ
แหน่งที่เหมาะสมของกลุ่มข้อมูลที่จัดเรียง  โดยขั้นตอนการทำงาน  เราจะนำเสนอด้วยการ
แสดงภาพพร้อมขั้นตอนการทำงานในแต่ละรอบ  โดยสมสุติว่ามีชุดตัวเลขที่ต้องการนำมา
จัดเรียงคือ  {23, 78, 45, 8, 32, 56}
               รอบที่ 1:
               เริ่มต้นจากข้อมูลต้นฉบับ  ซึ่งเป็นชุดตัวเลขที่ยังไม่ผ่านการจัดเรียง  กำแพง
หรือดรรชนีอยู่ที่ตำแหน่งสมาชิกลำดับที่ 2 ด้วยการเปรียบเทียบค่าตัวเลขช่องที่ 1 และช่อง
ที่ 2 ผลปรากฏว่าช่องที่ 2คือค่าตัวเลข 78 ซึ่งมีค่ามากกว่า 23 จึงถือว่าเรียงลำดับอยู่แล้ว 
ดังนั้นก็ให้ขยับกำแพงหรือดรรชนีไปอีกหนึ่งตำแหน่ง
               รอบที่ 2:
                   ตำแหน่งดรรชนี ณ ขณะนี้ขยับไปอยู่หน้าช่องที่ 3 ให้ทำการนำค่าตัวเลขจากช่อง
ที่ 3 ไปเปรียบเทียบกับชุดตัวเลขในส่วนที่จัดเรียงไว้แล้ว  ซึ่งอยู่ส่วนหน้า  ผลลัพธ์ที่ได้คือค่าตัว
เลข 45จะนำไปแทรกในตำแหน่งที่ 2 ซึ่งอยู่ระหว่างค่า 23 กับ 78
                รอบที่ 3:
                 
ตำแหน่งดรรชนีถูกขยับไปอยู่หน้าช่องที่ 4 ให้นำค่าตัวเลขจากช่องที่ 4ซึ่งใน
ที่นี้คือค่า8 ไปเปรียบเทียบกับชุดตัวเลขในส่วนที่จัดเรียงทั้งหมด  ผลปรากฏว่า ค่า 8  จะถูก
แทรกไว้ที่ตำแหน่งแรกในส่วนของข้อมูลที่ได้จัดเรียง
               
                รอบที่ 4:
                ตำแหน่งถัดไปคือช่วงที่ 5  ให้นำค่าตัวเลขจากช่องที่ 5 ซึ่งในที่นี้คือค่า 32ไป
เปรียบเทียบกับชุดตัวเลขในส่วนที่จัดเรียงทั้งหมด  ผลปรากฏว่า  ค่า 32 ซึ่งอยู่ตำแหน่งที่
5นี้จะนำไปแทรกไว้ที่ตำแหน่งในส่วนที่ได้จัดเรียงไว้โดยแทรกไว้หน้าค่า 45
                รอบที่ 5:
                รอบนี้จัดเป็นรอบสุดท้าย โดยขณะนี้เหลือเพียงข้อมูลตำแหน่งสุดท้ายเพียงตัว
เดียวที่จะต้องนำไปเปรียบเทียบเพื่อจัดเรียง  ผลปรากฏว่า  ค่าตัวเลข 56 จะถูกนำไปแทรก
ไว้ในตำแหน่งที่ 5 หลังจากนั้นก็จะได้ชุดตัวเลขที่ผ่านการจัดเรียงแล้วอย่างสมบูรณ์


4. การเรียงลำดับข้อมูลแบบ Bubble  Sort
                 ในการเรียงลำดับข้อมูลแบบ  Bubble  Sort  เป็นหลักการเรียงลำดับข้อมูลด้วย
การเปรียบเทียบข้อมูลเป็นคู่ที่อยู่ติดกันในแต่ละรอบการทำงาน  เพื่อสลับตำแหน่งกันหากอยู่
ผิดลำดับโดยหากเป็นการจัดเรียงลำดับข้อมูลจากน้อยไปหามาก  การทำงานจะเริ่มต้นจาก
ข้อมูลตัวสุดท้ายภายในลิสต์  และทำการเปรียบเทียบกับค่าถัดไปที่อยู่ข้างหน้าซึ่งอยู่ติดกัน 
โดยหากค่าตัวเลขที่อยู่ท้ายมีค่าน้อยกว่า  ก็จะทำการสลับตำแหน่ง  (Swap)กับตัวก่อนหน้า
เพื่อขยับลอยขึ้นไปซึ่งถ้ามองเป็นแนวดิ่งแล้วก็เสมือนกับว่า ค่าที่น้อยกว่าจะค่อย ๆ ลอยขึ้น
เหนือไปเรื่อย ๆ ซึ่งเปรียบเทียบกับฟองสบู่ที่ลอยขึ้นไปในอากาศนั่นเอง
  

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

5. การเรียงลำดับข้อมูลแบบ  Quick  Sort
                การเรียงลำดับข้อมูลแบบ   Bubble  Sort กับ  Quick  Sort  นั้น  ต่างก็เป็นวิธี
การเรียงลำดับข้อมูลแบบแลกเปลี่ยน (Exchange)แต่จะมีความแตกต่างกันตรงที่ การเรียง
ลำดับข้อมูลแบบ  Bubble Sort  นั้น จะทำการเปรียบเทียบค่าข้อมูลที่อยู่ติดกันและสลับตำ
แหน่งกันเพื่อให้ค่าตัวเลขน้อยๆลอยขึ้น แต่สำหรับ  Quick Sort นั้น จะใช้หลักการแบ่งส่วน
(Partition)ข้อมูลเป็นหลักซึ่งมีประสิทธิภาพมากกว่า เพราะว่าจำนวนของการสลับตำแหน่ง
จะมีน้อยกว่าการจัดเรียงแบบ  Bubble Sort
                แต่ละรอบของการทำงานของ  Quick  Sort   จะมีการเลือกอิลิเมนต์ตัวหนึ่งที่
เรียกว่า ค่า  Pivotที่ใช้สำหรับเป็นตัวแบ่งแยกส่วนข้อมูล  ซึ่งข้อมูลที่ถูกแบ่งส่วนนั้นอาจจะ
มีจำนวนอิลิเมนต์ที่ไม่เท่ากันก็ได้ โดยการแบ่งส่วนภายในลิสต์  จะแบ่งออกเป็น 3 ส่วนย่อย
ด้วยกัน ซึ่งสามารถอธิบายรายละเอียดในแต่ละข้อดังนี้
1. ส่วนที่หนึ่ง คือกลุ่มอิลิเมนต์ที่สมาชิกข้อมูลมีค่าน้อยกว่าค่า Pivot  Key
2. ส่วนที่สอง คือค่า Pivot  Key ที่ใช้เป็นค่าสำหรับแยกส่วนข้อมูล
    ซึ่งปกติแล้วตำแหน่งที่เหมาะสมของค่านี้จะอยู่ระหว่างลิสต์ที่มีค่าน้อยกว่าค่า Pivot  Key
    กัลิสต์ที่มีค่ามากกว่าหรือเท่ากับค่า Pivot  Key
3. ส่วนที่สาม คือกลุ่มอิลิเมนต์ที่สมาชิกข้อมูลมีค่ามากกว่าหรือเท่ากับค่าของ Pivot  Key
                        


 ดังนั้นตำแหน่งกึ่งกลางในลิสต์จากสูตร  set  mid  to (left+right)/2 จาก
ชุดคำสั่งลำดับที่ 1ในอัลกอริทึมที่ 9.5 จะได้เท่ากับ (1+12)/2 ก็คือตำแหน่งที่ 6 ดังนั้นก็
จะได้ Left Key = 78, Mid  Key = 62และ Right Key = 22  แต่ว่าทั้งสามอิลิเมนต์นั้น
ยังอยู่ในตำแหน่งที่ยังไม่ถูกต้อง  จึงต้องดำเนินการเปรียบเทียบเงื่อนไขตามอัลกอริทึมที่
9.5 เพื่อหาค่ากึ่งกลางที่ถูกต้องที่แสดงได้ดังต่อไปนี้
                   เมื่อได้ตำแหน่ง Left Key, Mid  Key และ Right Key
                   เปรียบเทียบค่า Left Key  > Mid  Key หรือไม่  ถ้าใช่ให้สลับตำแหน่ง
                   เปรียบเทียบค่า Left Key  >Right  Key หรือไม่  ถ้าใช่ให้สลับตำแหน่ง
                   เปรียบเทียบค่า mid Key  >Right  Key หรือไม่  ถ้าใช่ให้สลับตำแหน่ง
6. การเรียงลำดับข้อมูลแบบ Merge Sort
                สำหรับวิธีการเรียงลำดับข้อมูลทั้งหมดที่กล่าวไว้ข้างต้นนั้น ล้วนแล้วแต่เป็นวิธี
การจัดเรียงข้อมูลแบบภายใน(Internal Sort) ทั้งสิ้นโดยข้อมูลจะอยู่ภายในหน่วยความ
จำหลักทั้งหมดในระหว่างการประมวลผลดังนั้นเนื้อหาต่อไปนี้จะกล่าวถึงวิธีการจัดเรียงข้อ
มูลแบบภายนอก (External Sort)ซึ่งเป็นวิธีการจัดเรียงข้อมูลที่อนุญาตให้ข้อมูลที่ถูกจัด
เรียงบางส่วนถูกจัดเก็บไว้ในหน่วยความจำสำรองในระหว่างการประมวลผลและมีข้อมูลอีก
ส่วนหนึ่งกำลังจัดเรียงอยู่ภายในหน่วยความจำหลัก และหนึ่งในวิธีการเรียงลำดับข้อมูลแบบ
ภายนอกนี้ก็คือ วิธี Merge Sort หรือการเรียงลำดับข้อมูลแบบผสานนั่นเอง
                 กระบวนการเรียงลำดับข้อมูลแบบ Merge Sort มักนำไปใช้งานกับข้อมูลที่ต้อง
การจัดเรียงในปริมาณมาก ๆ กล่าวคือข้อมูลทั้งหมดที่ต้องการจัดเรียงนั้น ไม่สามารถนำไป
ประมวลผลที่หน่วยความจำหลักได้ในคราวเดียว  ดังนั้นจึงต้องมีการนำข้อมูลบางส่วนไปประ
มวลผลที่หน่วยความจำหลัก  ในขณะที่ข้อมูลที่เหลือก็จะถูกจัดเก็บไว้ในหน่วยความจำสำรอง
                 การดำเนินงานพื้นฐานของการเรียงลำดับข้อมูลแบบ Merge Sort นั้น เป็น
กระบวนการนำไฟล์ข้อมูลสองไฟล์ที่จัดเรียงแล้ว  มารวมกันเพื่อจัดเรียงข้อมูลตามคีย์ที่จัด
เรียง กล่าวคือเป็นการอ่านข้อมูลจาก File-1 และ File-2 และนำมาผสานรวมกัน ด้วยการ
เก็บเป็นเอาต์พุตไฟล์ไว้ที่ File - 3 ซึ่งเป็นไปดังรูปที่ 8.12
   


จากรายละเอียดที่ได้อธิบายไว้ในข้างต้น เป็นขั้นตอนของการนำไฟล์มาผสาน
รวมกันและต่อไปนี้จะแสดงถึงกระบวนการจัดเรียงข้อมูลที่ยังไม่ได้ผ่านการจัดเรียงมาก่อน
ซึ่งเรียกว่าขั้นตอนของการแบ่งส่วน (Distribution Phase) โดยมีหลักการอยู่ว่า ให้ทำการ
แบ่งข้อมูลออกเป็นกลุ่มย่อยด้วยการแบ่งส่วนข้อมูลออกทีละครึ่งจนกระทั่งไม่สามารถแบ่ง
ได้อีก จากนั้นก็จะเป็นขั้นตอนของการนำไฟล์มาผสานกัน (Merge Phase) เพื่อจะได้ไฟล์
ข้อมูลที่จัดเรียงเพียงไฟล์เดียวดังที่ได้กล่าวมาแล้วในข้างต้น
                     โดยสมมติว่า มีข้อมูลที่ต้องการนำมาจัดเรียงดังนี้คือ {1, 5, 3, 14, 17, 6, 7,
13}ซึ่งขั้นตอนการจัดเรียงเริ่มต้นด้วยการแบ่ง และท้ายสุดก็นำไฟล์มาผสานกัน ซึ่งเป็นไปดัง
รูปที่8.13 จากรูปที่ 8.13 จะเห็นขั้นตอนของการแบ่งขนาดของลิสต์ออกเป็นสองส่วนไปเรื่อย
ๆ ซึ่งเป็นการทำงานในลักษณะรีเคอร์ซีพ โดยมีการเรียกฟังก์ชันการทำงานแบบเดิมจำนวน
สองครั้ง และจะสิ้นสุดการทำงานแบบรีเคอร์ซีพเมื่อไม่สามารถแบ่งแยกได้อีก โดยจากรูปจะ
เห็นเส้นประแบ่งครึ่งซึ่งครึ่งแรกของภาพแสดงถึงการแบ่งส่วน ในขณะที่ครึ่งหลังของภาพ
แสดงถึงการผสานรวมกัน
         


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

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