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