MERGE SORT

MERGE SORT

merge sort เป็นวิธีการเรียงข้อมูลที่มีความสำคัญมาก เพราะเป็นวิธีสำคัญในการเรียงข้อมูลขนาดใหญ่ (การเรียงแบบภายนอก) วิธีการเรียงจะเริ่มกระทำครั้งละ 2 ค่า ซึ่งจะได้ลิสต์ย่อยจำนวน n/2 ลิสต์ แต่ละลิสต์มี 2 ค่า จากนั้นจะทำการ merge sort ต่ออีกครั้งละ 2 ลิสต์แล้วจะได้ลิสต์ที่เรียงแล้ว จำนวน n/4 ลิสต์ แต่ละลิสต์มี 4 ค่า ทำเช่นนี้ไปเรื่อย ๆ จนในที่สุดจะทำการ merge sort 2 ลิสต์ สุดท้ายเข้าด้วยกัน จะได้ลิสต์ที่เรียงแล้ว

จะเห็นได้ว่าการทำ merge sort ต้องกระทำเป็นจำนวน O(log 2 n) เที่ยว และแต่ละเที่ยวที่ทำการ merge สามารถกระทำได้ใน O(n) ดังนั้นเวลาในการเรียงข้อมูลจะเป็น O(n log2n)





*เครดิต [Only admins are allowed to see this link]


ขั้นตอนวิธี Merge sort
Merge sort เป็นวิธีการจัดเรียงข้อมูลที่ใช้หลักการ divide-and-conquer นั่นคือปัญหาจะถูกแบ่งออกเป็น ปัญหาย่อยขนาดเล็ก โดยใช้นิยามเวียนเกิดในการแก้ปัญหาย่อยเหล่านี่ ปัญหาหลังจากถูกแบ่งให้มีขนาดเล็กพอเหมาะแล้ว เราสามารถหาคำตอบได้โดยง่าย เรากำหนดการเรียกใช้ ขั้นตอนวิธีดังนี้ MERGE-SORT(A, p, r) เมื่อ A เป็น array และ p, r เป็นดัชนี ที่บอกการเรียงใน array A ที่ต้องการทำงาน
ข้อมูลเข้า A[1..n], p, r
ข้อมูลออก การจัดเรียงของข้อมูลใน A โดยที่ A[p] A[p+1] A[p+2] . . . A[r] (sorted in place)
MERGE-SORT(A, p, r)
1. if p < r
2. then q = floor((p+r)/2)
3. MERGE-SORT(A, p, q)
4. MERGE-SORT(A, q+1, r)
5. MERGE(A, p, q, r)
6. endif
MERGE(A, p, q, r)
1. m = r - p + 1
2. Create Temp[1..m]
3. (i, j, k) = (p, q+1, 1)
4. while(i <= q and j <= r)
5. if A[i] > A[j]
6. (Temp[k], k, j) = (A[j], k+1, j+1)
7. else
8. (Temp[k], k, i) = (A[i], k+1, i+1)
9. end if
10. end while
11. if(j <= r)
12. while(j <= r)
13. (Temp[k], k, j) = (A[j], k+1, j+1)
14. endwhile
15. else
16. while(i <= q)
17. (Temp[k], k, i) = (A[j], k+1, i+1)
18. endwhile
19. endif
20. for i = 1 to m
21. A[i+p-1] = Temp[i]
22. endfor

*เครดิต [Only admins are allowed to see this link]