Mergesort

[wkid]

Mergesort เป็นอัลกอริทึม ที่จัดการกับข้อมูลในรูปแบบของการรวมข้อมูล 2 ก้อน
ให้มาอยู่ในก้อนเดียวกัน ซึ่งข้อมูลแต่ละก้อน จะถูกจัดเรียงเข้าด้วย ก็จะต้องมีการจัดการ
ข้อมูลแต่ละก้อนเรียบร้อยแล้ว คือมีการเรียงลำดับของข้อมูลเรียบร้อยแล้วนั่นเอง
แต่รอบในการทำงานของ ถือว่าใช้เวลาทำงานได้ดีเลยทีเดียว ซึ่งเดี๋ยวเราจะมาดูการทำงาน
ของ Mergesort ว่าจะมีการทำงานยังไง มาดูกัน

ในการทำงานของ Mergesort สมมติให้ ว่ามีข้อมูล

ตัวอย่างข้อมูล

ข้อมูล.jpg (3.12 KiB) Viewed 252 times

1. เริ่มจากแบ่งข้อมูลออกเป็น 2 ส่วน จะได้

   

   การแยกข้อมูล

   ข้อมูล1.jpg (3.07 KiB) Viewed 252 times

2. ทำการแยกข้อมูลไปเรื่อยๆ จนกว่าจะเหลทือข้อมูลเป็น 1 ตัว

   

   แยกจนเป็น 1 ตัว

   ข้อมูล 3.jpg (3.77 KiB) Viewed 252 times

3. รวมกันตามที่ได้แบ่งมาโดยการที่จะเทียบกันตามตำแหน่ง เช่น
   [1,3] กับ [2,4] ก็จะเอาตำแหน่งที่ 0 คือ 1และ2 มาเที่ยบกัน
   ก็จะนำค่าที่น้อยกว่าไปเก็บไว้ จะได้
   [1,3] กับ [2,4] แต่จะข้อมูลใหม่ = [1] เป็นต้น หาตัวไหนถูกเก็บค่า
   ก็จะถูกขยับไปตำแหน่งถัดไป
4. หลังจากนั้นก็จะทำจนกว่าจะเก็บข้อมูลทั้งหมดไว้ด้วยกัน ก็จะได้

   

   ข้อมูลที่รวมเสร็จ

   ข้อมูล 4.jpg (3.09 KiB) Viewed 252 times

สรุปได้ว่า การทำงานของ Mergesort อัลกอริทึมกับข้อมูลได้ค่อนข้างดี และใช้เวลาในการรัน เท่ากับ
บิ๊กO ของ NlogN โดยการทำงานได้ดีและเร็วจะขึ้นอยู่กับการจัดการกับข้อมูลหาข้อมูลทั้ง 2
มีการจัดการมาเรียบร้อยก็จะทำงานได้รวดเร็ว จึงเหมาะกับงานที่มีข้อมูล 2 ก้อน
ที่มีควาามยุ่งยากของข้อมูลน้อย หรือข้อมูลทั้ง 2 ก้อน ถูกจัดเรียงข้อมูลมาเรียบร้อยแล้ว
เพื่อให้ตัวของ Mergesort มีการทำงานที่ทำให้ทำได้ไวที่สุด เป็นต้นครับ

อ้างอิง
https://degas.en.kku.ac.th/courses/EN812303/Chap7%20Sorting.pdf
https://en.wikipedia.org/wiki/Merge_sort
https://www.geeksforgeeks.org/merge-sort/