Trong bài này mình sẽ reviews đến các bạn thuật toán thu xếp trộn (Merge Sort). Đây là một trong những thuật toán thu xếp trong C++.

Bạn đang xem: Merge sort là gì

*


*

Chúng ta sẽ cùng cả nhà tìm hiều về thu xếp trộn là gì cùng cách thực hiện thuật toán thu xếp trộn trong C++. Ở cuối bài viết, mình đang giải một bài bác toán ví dụ để chúng ta hiểu hơn về kiểu cách áp dụng thuật toán trong thực tế.

1. Sắp xếp trộn là gì?

Sắp xếp trộn là một trong những thuật toán sắp xếp dựa trên giải mã Divide and Conquer (Chia nhằm trị).

Thuật toán này sẽ chia mảng thành hai nữa rồi bố trí trên từng nữa một. Tiếp nối kết hợp chúng lại cùng nhau thành một mảng vẫn được sắp xếp.

Bài viết này được đăng trên


Ví dụ minh họa:

Như chúng ta đã thấy sinh hoạt hình trên, dãy số lúc đầu bao gôm các số: 38 27 43 3 9 82 10.

Chúng ta sẽ tạo thành hai phần là 1 trong bên 4 số với một mặt 3 số. Rồi tiếp tục chia 4 số kia thành nhị phần là mỗi mặt 2 số. Cứ phân tách như vậy cho đến khi được tác dụng như chiếc thứ 4.

Sau khi phân chia xong, bây chừ chúng ta bắt đầu vào việc so sinh từng phần nhỏ. Rồi gom chúng lại thành một hàng số hoàn chỉnh đã bố trí ở các dòng 5, 6, 7 như vào hình.

Sau lúc gom lại và so sánh chấm dứt ta được dãy số mới đã sắp tới xếp: 3 9 10 27 38 43 82.

2. Thuật toán thu xếp trộn (Merge Sort) vào C++

Trong phần này bản thân sẽ đưa ra quá trình để viết thuật toán, sau đó mình đang để thuật toán đang viết sẵn cho chúng ta dễ hình dung.

Giải mê say thuật toán

Trong thuật toán sẽ sở hữu hai bước đó là chia bộ phận và gộp phần tử (kèm theo sắp tới xếp). Cụ thể trong thuật toán mình viết hàm mergeSort() nhằm chia thành phần và hàm merge() để gộp, thu xếp phần tử.

Sử dụng đệ qui để chia danh sách thành nhị nửa cho đến khi không phân chia thêm được nữa (hàm mergeSorrt()).Tạo nhị mảng trong thời điểm tạm thời để cất các thành phần sau lúc chia, thuộc với chính là hai mảng con L cùng R.Trường đúng theo chỉ có 1 phần tử thì coi như đã được sắp xếp.Sau khi chia xong, sẽ gộp các thành phần ở mảng nhỏ R với L vào mảng chính arr.Kết hợp những list nhỏ dại đã bố trí với nhau thành một list mới. Sau khi kết hợp tiến hành bố trí chúng để liên tục cho lần kết hợp kế tiếp.

Code thuật toán bố trí trộn

Trong thuật toán tôi đã chú thích nạm thể, các chúng ta cũng có thể đọc để dễ hiểu hơn.


void merge(int arr<>, int l, int m, int r) int i, j, k; int n1 = m - l + 1; int n2 = r - m; int L, R;//tạo 2 mảng tạm thời để đựng các bộ phận sau khi chia // Copy dữ liệu sang những mảng lâm thời for (i = 0; i

3. Ví dụ bố trí trộn vào mảng

Chúng ta sẽ vận dụng thuật toán vẫn viết nghỉ ngơi trên, để viết một chương trình bố trí các bộ phận trong mảng được nhập từ bàn phím.

Xem thêm: Trong Đồ Hoạ Render Nghĩa Là Gì ? Kiến Thức Nền Tảng Về Lĩnh Vực Thiết Kế Đồ Họa

Tương từ bỏ như những bài trước, chỉ cần thay thế các thuật toán khác bằng thuật toán mergeSort() là được.

Code mẫu:


#include#include#include using namespace std;// bọn họ cần gồm hai mảng con vì vậy nên tạo nhì mảng con arr và arr. Tiếp nối gộp chúng lạivoid merge(int arr<>, int l, int m, int r) int i, j, k; int n1 = m - l + 1; int n2 = r - m; int L, R;//tạo 2 mảng trong thời điểm tạm thời để đựng các thành phần sau khi phân tách // Copy tài liệu sang những mảng tạm bợ for (i = 0; i > n; while(n > a; ; cout
Kết quả:

Như vậy là họ đã thực hiện chấm dứt chương trình sắp xếp các bộ phận trong mảng, sử dụng phương thức sắp xếp trộn. Cũng như kết thúc hướng dẫn thuật toán bố trí trộn vào C++. Chúc chúng ta thực hiện tại thành công!!!