cấu trúc dữ liệu và giải thuật merge sort_MergeSort.pptx

cấu trúc dữ liệu và giải thuật merge sort

1. ĐẠI HỌC KINH DOANH VÀ CÔNG NGHỆ HÀ NỘI NHÓM 2 Môn học : Cấu trúc dữ liệu và giải thuật Sắp xếp Trộn trực tiếp (Merge Sort)

2. Giới thiệu thuật toán Merge Sort Merge sort là một thuật toán chia để trị. Thuật toán này chia mảng cần sắp xếp thành 2 nửa. Tiếp tục lặp lại việc này ở các nửa mảng đã chia. Sau cùng gộp các nửa đó thành mảng đã sắp xếp. Hàm merge() được sử dụng để gộp hai nửa mảng. Hàm merge(arr, l, m, r) là tiến trình quan trọng nhất sẽ gộp hai nửa mảng thành 1 mảng sắp xếp, các nửa mảng là arr[l…m id ] và arr[m id +1…r] sau khi gộp sẽ thành một mảng duy nhất đã sắp xếp.

3. 4 2 7 9 a [n] = 10 5 8 6 M ô tả thuật toán : Ta nhập vào 1 mảng như sau :

4. 4 2 7 9 left mid right a [n] = 4 2 7 9 10 5 8 6

5. 4 2 7 9 10 5 8 6 left mid right a [n] = 4 2 7 9 left mid right 4 2 left mid right

6. 4 2 7 9 10 5 8 6 left mid right a [n] = 4 2 7 9 left mid right 4 2 left mid right

7. 4 2 7 9 10 5 8 6 left mid right a [n] = 2 4 left mid right 7 9

8. 4 2 7 9 10 5 8 6 left mid right a [n] = left mid right 7 9 left mid right 2 4 7 9

9. 4 2 7 9 10 5 8 6 left mid right a [n] = 2 4 7 9 left mid right 7 9 left mid right

10. 4 2 7 9 10 5 8 6 left mid right a [n] = left mid right 2 4 7 9

11. 4 2 7 9 10 5 8 6 left mid right a [n] = left mid right 2 4 7 9

12. 2 4 7 9 left mid right a [n] = 10 5 8 6

13. 2 4 7 9 left mid right a [n] = 10 5 8 6 10 5 8 6 left mid right

14. 2 4 7 9 left mid right a [n] = 10 5 8 6 10 5 left mid right 8 6 10 5 left mid right

15. 2 4 7 9 left mid right a [n] = 10 5 8 6 10 5 left mid right 8 6 10 5 left mid right

16. 2 4 7 9 left mid right a [n] = 10 5 8 6 5 10 left mid right 8 6

17. 2 4 7 9 left mid right a [n] = 10 5 8 6 5 10 left mid right 8 6 8 6 left mid right

18. 2 4 7 9 left mid right a [n] = 10 5 8 6 5 10 left mid right 8 6 8 6 left mid right

19. 2 4 7 9 left mid right a [n] = 10 5 8 6 5 10 left mid right 6 8

20. 2 4 7 9 left mid right a [n] = 10 5 8 6 5 10 left mid right 6 8

21. 2 4 7 9 left mid right a [n] = 5 6 8 10

22. 2 4 7 9 5 6 8 10 left mid right 2 4 7 9 5 6 8 10 L [n1] = R [n2] = a [n] = 2 4 7 9 5 6 8 10 a [n] = i j k

23. 2 4 7 9 5 6 8 10 left mid right 2 4 7 9 5 6 8 10 L [n1] = R [n2] = a [n] = a [n] = i j 2 k 4 8 5 6 9 7 10

24. 2 4 7 9 5 6 8 10 left mid right 2 4 7 9 5 6 8 10 L [n1] = R [n2] = a [n] = a [n] = i j 2 k 4 8 5 6 9 7 10

25. 2 4 7 9 5 6 8 10 left mid right 2 4 7 9 5 6 8 10 L [n1] = R [n2] = a [n] = a [n] = i j 2 k 4 8 5 6 9 7 10

26. 2 4 7 9 5 6 8 10 left mid right 2 4 7 9 5 6 8 10 L [n1] = R [n2] = a [n] = a [n] = i j 2 k 4 8 5 6 9 7 10

27. 2 4 7 9 5 6 8 10 left mid right 2 4 7 9 5 6 8 10 L [n1] = R [n2] = a [n] = a [n] = i j 2 k 4 8 5 6 9 7 10

28. 2 4 7 9 5 6 8 10 left mid right 2 4 7 9 5 6 8 10 L [n1] = R [n2] = a [n] = a [n] = i j 2 k 4 8 5 6 9 7 10

29. 2 4 7 9 5 6 8 10 left mid right 2 4 7 9 5 6 8 10 L [n1] = R [n2] = a [n] = a [n] = i j 2 k 4 8 5 6 9 5 10

30. 2 4 7 9 5 6 8 10 left mid right 2 4 7 9 5 6 8 10 L [n1] = R [n2] = a [n] = a [n] = i j 2 k 4 8 5 6 9 5 10

31. 2 4 7 9 5 6 8 10 left mid right 2 4 7 9 5 6 8 10 L [n1] = R [n2] = a [n] = a [n] = i j 2 k 4 8 5 6 6 5 10

32. 2 4 7 9 5 6 8 10 left mid right 2 4 7 9 5 6 8 10 L [n1] = R [n2] = a [n] = a [n] = i j 2 k 4 8 5 6 6 5 10

33. 2 4 7 9 5 6 8 10 left mid right 2 4 7 9 5 6 8 10 L [n1] = R [n2] = a [n] = a [n] = i j 2 k 4 8 7 6 6 5 10

34. 2 4 7 9 5 6 8 10 left mid right 2 4 7 9 5 6 8 10 L [n1] = R [n2] = a [n] = a [n] = i j 2 k 4 8 7 6 6 5 10

35. 2 4 7 9 5 6 8 10 left mid right 2 4 7 9 5 6 8 10 L [n1] = R [n2] = a [n] = a [n] = i j 2 k 4 8 7 8 6 5 10

36. 2 4 7 9 5 6 8 10 left mid right 2 4 7 9 5 6 8 10 L [n1] = R [n2] = a [n] = a [n] = i j 2 k 4 8 7 8 6 5 10

37. 2 4 7 9 5 6 8 10 left mid right 2 4 7 9 5 6 8 10 L [n1] = R [n2] = a [n] = a [n] = i j 2 k 4 9 7 8 6 5 10

38. 2 4 7 9 5 6 8 10 left mid right 2 4 7 9 5 6 8 10 L [n1] = R [n2] = a [n] = a [n] = i j 2 k 4 9 7 8 6 5 10

39. 2 4 7 9 5 6 8 10 left mid right 2 4 7 9 5 6 8 10 L [n1] = R [n2] = a [n] = a [n] = i j 2 k 4 9 7 8 6 5 10

40. a [n] = 2 4 9 7 8 6 5 10 Mảng đã được sắp xếp

41. Thanks!