Merge sort là gì? Thuật toán sắp xếp trộn Merge sort trong C/C++

Lập trìnhMerge sort là gì? Thuật toán sắp xếp trộn Merge sort trong...

Ngày đăng:

0
(0)

Merge sort là phép toán được sử dụng khá phổ biến trong ngôn ngữ C/C++. Bài viết DINHNGHIA.COM.VN này sẽ giúp bạn hiểu rõ hơn về Merge sort để có thể vận dụng vào trong công việc nhé!

Merge sort là gì? Thuật toán sắp xếp trộn Merge sort trong C/C++
Merge sort là gì? Thuật toán sắp xếp trộn Merge sort trong C/C++

Sắp xếp trộn – Merge sort là gì?

Khái niệm

Merge sort hay còn được gọi là thuật toán sắp xếp trộn được hình thành và phát triển sự trên giải thuật chia để trị (Divide and conquer). Thuật toán này sẽ chia mang ra thành từng phần, sau đó tiến hành sắp xếp và trộn vào với nhau.

Sắp xếp trộn (Merge sort)
Sắp xếp trộn (Merge sort)

Có thể bạn quan tâm:

Ý tưởng

Thuật toán Merge sort chia mảng dữ liệu thành hai nửa (có thể bằng nhau hoặc chênh nhau 1 phần tử nếu mảng lẻ), sau đó lần lượt tiến hành sắp xếp trên từng phần một, sau đó kết hợp chúng lại với nhau thành một mảng hoàn chỉnh theo thứ tự sắp xếp.

Giải thuật

Bước 1: Tách đôi mảng ra làm hai phần bằng hoặc tương đương nhau và lưu vào 2 mảng tạm

Bước 2: Dùng đệ quy để chia nhỏ các phần đó ra cho đến khi không thể chia được nữa thì dừng lại

Lưu ý: Trong trường hợp bị lẻ một giá trị thì chúng ta xem như giá trí đó đã được sắp xếp.

Bước 3: Sau khi chia nhỏ ra, bạn tiến hành sắp xếp các giá trị của hai phần lại và gộp lại thành một mảng chung

Bước 4: Kết hợp các giá trị con đã được sắp xếp với nhau thành một mảng mới.

Bước 5: Sau khi kết hợp lại, ta chỉ cần sắp xếp chúng để tiếp tục cho lần kết hợp kế tiếp.

Ví dụ thuật toán sắp xếp trộn (Merge sort)
Ví dụ thuật toán sắp xếp trộn (Merge sort)

Cách viết thuật toán sắp xếp trộn Merge sort

Code: Thuật toán sắp xếp trộn merge sort

Gợi ý:

  • Sử dụng đệ qui để chia danh sách các phần tử thành hai nửa cho đến khi không chia thêm được nữa.
  • 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 (trái) và R (phải).
  • 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.
  • Kết hợp các danh sách nhỏ đã sắp xếp với nhau thành một danh sách 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.
Input và Output
Input và Output

Xem thêm:

Hy vọng bài viết này sẽ giúp bạn làm chủ được Merge Sort để ứng dụng vào công việc một cách hiệu quả nhất nhé. Chúc các bạn thực hiện thành công!

Bạn thấy bài viết này hữu ích chứ?

Hãy chọn vào ngôi sao để đánh giá bài viết

Đánh giá trung bình 0 / 5. Lượt đánh giá 0

Hãy là người đầu tiên đánh giá bài viết

Hãy để lại bình luận

Xem nhiều

Bài tin liên quan

1m2 bằng bao nhiêu km2? Chuyển đổi mét vuông sang kilo mét vuông

Mét vuông và ki-lô-mét vuông là đơn vị đo...

1 hg bằng bao nhiêu g, mg, ng? Cách quy đổi nhanh, chuẩn xác

Đơn vị cân lường hectogram thường thấy trong nhiều...

Hướng dẫn quy đổi Mét trên giây sang Centimet trên giây chuẩn

Đơn vị m/s và cm/s đóng vai trò quan...

1m bằng bao nhiêu inch? Hướng dẫn chuyển đổi mét sang inch

Trong nhiều lĩnh vực, đơn vị mét thường được...