Merge Sort là một trong những thuật toán sắp xếp, độ khó phức tạp trung bình và đạt về hiệu quả thời gian, và hiệu năng. Do đó với những chương trình yêu cầu độ tối ưu cao thì Merge Sort là một lựa chọn tốt. Bài này chúng ta sẽ hiểu rõ hơn về Merge Sort và cách sử dụng bằng ngôn ngữ C++
Lưu ý: Bài viết chỉ mô tả cho việc sắp xếp dãy số tăng dần bằng ngôn ngữ C++.
Bạn đang xem: Merge sort là gì
Tìm hiểu thuật toán Merge Sort
Giống như Quick sort, Merge sort là một thuật toán dùng để sắp xếp dãy số, và cũng chia nhỏ mảng ra nhiều mảng nhỏ để xử lý. Thuật toán này cũng 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. Để gộp các nữa đó thành 1 mảng hoàn chỉnh, chúng ta sẽ sử dụng tiếp hàm merge() để gộp hai nửa mảng. Hàm merge(arr, l, m, r) là bước quan trọng nhất để gộp 2 nửa mảng thành 1 mảng.
Ví dụ các bước của thuật toán sắp xếp merge sort
Nếu bạn chưa hiểu tư tưởng của Merge sort. Đừng lo lắng, chúng ta sẽ đi đến ví dụ hình ảnh sau
merge sort
Hình ảnh trên đây là ví dụ 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, chúng ta thấy mảng ban đầu được tách ra nhỏ cho đến khi kích thước các mảng con la 1. Sau đó bắt đầu gộp lại cho đến khi được 1 mảng theo thứ tự tăng dần.
Xem thêm: Woocommerce Là Gì – Tổng Quan Về Woocommerce
Chúng ta có 1 mảng lớn là {38, 27, 43, 3, 9, 82, 10}.Tách ra làm 2 mảng nhỏ hơn là arr1 = , arr2 = .Tách arr1 làm 2 mảng nhỏ hơn và arr 2 làm 2 mảng nhỏ hơn.Lặp đi lặp lại, đến khi mảng nhỏ nhất còn 1 phần tử.Bắt đầu ghép 2 các mảng lại với nhau sử dụng hàm Merge() theo thứ tự từ nhỏ tới lớnSau cùng chúng ta có 1 mảng hoàn chỉnh theo thứ tự {3, 9, 10, 27, 38, 43, 82}
Vậy hàm merge() là hàm gì? và có thể ghép các chuỗi theo thứ tự
Dưới đây là code mẫu C++, chưa thuật toán hàm merge và sắp xếp theo thuật toán merge sorte
#include#include // Gộp hai mảng con arr và arrvoid merge(int arr, int l, int m, int r){ int i, j, k; int n1 = m – l + 1; int n2 = r – m; /* Tạo các mảng tạm */ int L, R; /* Copy dữ liệu sang các mảng tạm */ for (i = 0; i
Ưu và nhược điểm của thuật toán Merge Sort:
Ưu điểm: Sắp sếp nhanh hơn so với các thuật toán cơ bản (Insertion Sort, Selection Sort, Interchage Sort), và đôi khi nhanh hơn Quick Sort trong một số trường hợp.Nhược điểm: thuật toán khó cài đặt, không nhận dạng được mảng đã được sắp, nhìn chung khó hơn các thuật toán khác.
Xem thêm: Gis Là Gì – Gis Cho Người Mới Bắt đầu
Trả lời Hủy
Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *
Bình luận
Tên *
Email *
Trang web
Lưu tên của tôi, email, và trang web trong trình duyệt này cho lần bình luận kế tiếp của tôi.
Chuyên thiết kế website chuẩn SEO chất lượng. Hỗ trợ SEO lên top Google. Hàng đầu về xây dựng thương hiệu marketing, Ads và SEO
Chuyên mục: Hỏi Đáp
