Thuật toán sắp xếp merge kind là 1 trong những thuật toán có độ phức tạp trên mức trung bình và cùng sử dùng phương pháp chia để trị giống thuật toán sắp xếp nhanh fast kind. Thuật toán này ko chỉ vận dụng trong sắp xếp mà còn trên nhiều bài toán khác. Hãy cùng tìm tôi tìm hiểu nhé.
Chào mừng người dùng quay trở lại sở hữu weblog của Nguyễn Văn Hiếu. Đây là 1 bài viết trong collection những thuật toán sắp xếp có minh họa code dùng ngôn ngữ lập trình C++.
Trên bài viết này Nguyễn Văn Hiếu xin giới thiệu tới người dùng thuật toán sắp xếp merge kind. Đây là 1 thuật toán siêu sắp xếp siêu hay và có độ phức tạp thấp hơn.
Lưu ý: Bài viết chỉ mô tả cho việc sắp xếp dãy số nâng cao dần. Việc sắp xếp dãy số giảm dần sẽ tương tự động và bạn đọc tự động tìm hiểu
Ý tưởng của thuật toán merge kind
Giống như Fast kind, Merge kind là 1 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 trên những nửa mảng đã chia. Sau cùng gộp những nửa ấy thành mảng đã sắp xếp. Hàm merge() được dùng để gộp 2 nửa mảng. Hàm merge(arr, l, m, r) là tiến trình quan yếu nhất sẽ gộp 2 nửa mảng thành 1 mảng sắp xếp, những nửa mảng là arr[l…m] và arr[m+1…r] sau khoản thời gian gộp sẽ thành 1 mảng duy nhất đã sắp xếp.
Hãy xem ý tưởng triển khai code dưới đây để hiểu hơn
Hình ảnh dưới đây từ wikipedia sẽ hiển thị cho bạn toàn bộ sơ đồ tiến trình của thuật toán merge kind cho mảng {38, 27, 43, 3, 9, 82, 10}. Trường hợp nhìn kỹ hơn vào sơ đồ này, chúng ta có thể thấy mảng ban đầu được lặp lại hành động chia cho tới lúc kích thước những mảng sau chia là 1. Lúc kích thước những mảng con là 1, tiến trình gộp sẽ khởi đầu thực hành gộp lại những mảng này cho tới lúc hoàn thành và chỉ còn 1 mảng đã sắp xếp.
Phương pháp hàm merge hoạt động lúc gộp 2 mảng con
Sở hữu trường hợp lúc 2 mảng con chỉ có 1 phần tử, ta chỉ việc xem phần tử nào bé hơn và đẩy lên đầu, phần tử còn lại đặt phía sau. Do vậy, những mảng con cần gộp lại có tính chất luôn được sắp nâng cao dần.
Xem thêm: Chuyên phần cấu trúc dữ liệu và giải thuật
Minh họa thuật toán sắp xếp fast kind dùng C/C++
Đánh giá thuật toán sắp xếp merge kind
Độ phức tạp thuật toán
- Trường hợp phải chăng: O(nlog(n))
- Trung bình: O(nlog(n))
- Trường hợp xấu: O(nlog(n))
Ko gian bộ nhớ dùng: O(n)
Tài liệu tham khảo
- https://www.geeksforgeeks.org/merge-sort/
- http://bigocheatsheet.com/
