บ้านช่วยเหลือรายชื่อสมาชิกกลุ่มผู้ใช้สมัครสมาชิก(Register)เข้าสู่ระบบ(Log in)

Share | 
 

 MERGE SORT

อ่านหัวข้อก่อนหน้า อ่านหัวข้อถัดไป Go down 
ผู้ตั้งข้อความ
Angel-beats
ﻬ௫ﻬAdminﻬ௫ﻬ
ﻬ௫ﻬAdminﻬ௫ﻬ


ชื่อในเกม : Novas
ค่าขยัน : 35
ค่าขนม : -1869
คะแนน : 0

ตั้งหัวข้อเรื่อง: MERGE SORT   25/7/2012, 18:44

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]
ขึ้นไปข้างบน Go down
ดูข้อมูลส่วนตัว http://virgin.wow3.info
 
MERGE SORT
อ่านหัวข้อก่อนหน้า อ่านหัวข้อถัดไป ขึ้นไปข้างบน 
หน้า 1 จาก 1

Permissions in this forum:คุณไม่สามารถพิมพ์ตอบ
Vїяġїи Ĝϋί£Ð :: General Zone :: Dev C++-
ไปที่: