Thuật Toán Merge Sort( Sắp Xếp Trộn (Merge Sort), Thuật Toán Sắp Xếp Trộn (Merge Sort)

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

Đang xem: Sắp xếp trộn

Chúng ta sẽ cùng nhau tìm hiều về sắp xếp trộn là gì và cách triển khai thuật toán sắp xếp trộn trong C++. Ở cuối bài viết, mình sẽ giải một bài toán cụ thể để các bạn hiểu hơn về 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 thuật toán sắp xếp dựa trên giải thuật Divide and Conquer (Chia để trị).

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

Ví dụ minh họa:

Như các bạn đã thấy ở hình trên, dãy số ban đầu bao gôm các số: 38 27 43 3 9 82 10.

Chúng ta sẽ chia thành hai phần là một bên 4 số và một bên 3 số. Rồi tiếp tục chia 4 số đó thành hai phần là mỗi bên 2 số. Cứ chia như vậy cho đến khi được kết quả như dòng thứ 4.

READ:  Tải Game Cổng Zing Play : Cổng Giải Trí Đa Dạng, Cổng Game Zingplay

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

Xem thêm: How To Activate Microsoft Office 2013 Product Key In 2020, Office 2013: Installing On Windows

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

2. Thuật toán sắp xếp trộn (Merge Sort) trong C++

Trong phần này mình sẽ đưa ra các bước để viết thuật toán, sau đó mình sẽ để thuật toán đã viết sẵn cho các bạn dễ hình dung.

Giải thích thuật toán

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

Quảng cáo

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

READ:  Conversion Rate Là Gì ? 5 Cách Tối Ưu Tốt Nhất Conversion Là Gì

Code thuật toán sắp xếp trộn

Trong thuật toán mình đã chú thích cụ thể, các bạn 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 để chứa các phần tử sau khi chia // Copy dữ liệu sang các mảng tạm for (i = 0; i

3. Ví dụ sắp xếp trộn trong mảng

Chúng ta sẽ áp dụng thuật toán đã viết ở trên, để viết một chương trình sắp xếp các phần tử trong mảng được nhập từ bàn phím.

Xem thêm: Học Lỏm Những Màu Tóc Nhuộm Của Sao Hàn Là Biết 6 Màu Tóc Nhuộm Siêu Thời Thượng

Tương tự như các 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.

Quảng cáo

Code mẫu:

#include#include#include using namespace std;// Chúng ta cần có hai mảng con vì vậy cần tạo hai mảng con arr và arr. Sau đó 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 tạm thời để chứa các phần tử sau khi chia // Copy dữ liệu sang các mảng tạm for (i = 0; i > n; }while(n > a; }; cout
Kết quả:

Như vậy là chúng ta đã thực hiện xong chương trình sắp xếp các phần tử 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 sắp xếp trộn trong C++. Chúc các bạn thực hiện thành công!!!

READ:  Vi Phạm Dân Sự Do Vi Phạm Hợp Đồng, Vi Phạm Dân Sự Là Gì

Quảng cáo

Bài trước Bài tiếp

Quảng cáo

QUẢN TRỊ WEB
» Quản trị Linux
» Thủ thuật Hosting
» Kiến thức Domain
» Windows
» Bảo mật
WEB FRONTEND
» Javascript
» AngularJS
» jQuery
» jQuery Mobile
» HTML & CSS
» Bootstrap
» TypeScript
» SASS CSS
» VueJS
» NestJS
» Học ReactJS
WEB BACKEND
» PHP
» Codeigniter
» Laravel
» WordPress
» Phalcon
» OpenCart
» NodeJS
» Blogspot
DATABASE
» Học MySQL
» Học MongoDB
» CSDL căn bản
» Học Oracle
» Học SQL Server
» Học SQLite
PROGRAMMING
» Python
» Java
» Pascal
» Học C#
» Học Ruby
» Học Swift
» C / C++
» Kotlin
» Golang
» Giải thuật
» Visual Basic
MOBILE DEV
» React Native
» Học iOS
» Android
CÔNG CỤ
» Học Git
» Testing
» Control Panel
» Dev Tool
» FFmpeg
TIN HỌC
» Excel
» Word
» PowerPoint
» Access
» Photoshop
MÔN HỌC
» Tiếng Anh
» Toán
» Tiếng Nhật
» Văn học
Advertisements

Quảng cáo

Giới thiệu
Giới thiệu Liên hệ Chính sách Điều khoản Guest Post
Liên kết
Thủ thuật Download Game Ứng dụng Tin học Môn học
Hosting
Tinohost Azdigi Vultr INET
Khóa học
PHP AZ Laravel Frontend FullStack Javascript jQuery Javascript NodeJS + ReactJS

*

Xem thêm bài viết thuộc chuyên mục: tin tổng hợp