[ Sort ] Thuật toán Merge-Sort [Code C++]

 Thuật toán Merge-Sort [Xem clip hướng dẫn và demo]

+ Tư tưởng của thuật toán Merge-Sort

Mô tả bài toán: cho 2 danh sách A và B lần lượt có m và n phần tử đã sắp xếp theo thứ tự. Bài toán đặt ra trộn 2 danh sách A và B với nhau thành danh sách C cũng là một danh sách có thứ tự.

+ Thuật toán:

Bước 1: khởi tạo ba chỉ số chạy trong vòng lặp i = 0, j = 0, k = 0 tương ứng cho ba mảng A, B và C.
Bước 2: tại mỗi bước nếu cả hai chỉ số (i<m và j<n) ta chọn min(A[i],B[j]) và lưu nó vào trong C[k]. Chuyển sang Bước 4.
Bước 3: tăng giá trị k lên 1 và quay về Bước 2.
Bước 4: sao chép tất cả các giá trị còn lại từ các danh sách mà chỉ số còn vi phạm (tức i<m hoặc j<m) vào trong mảng C.

Hình minh họa:

+ Cài đặt thuật toán [Code C++]

#include <iostream.h>
#include <conio.h>
#define max 100
// nhap day
void NhapMang(int A[],int n) {
for(int i=0; i<n; i++) {
cout<<"Phan tu "<<i<<" = ";
cin>>A[i];
}
}
// in day
void XuatMang(int A[],int n) {
cout<<endl;
for(int i=0; i<n; i++)
cout<<A[i]<<"\t";
}
// merge sort
void MergeSort(int m, int n, int &k, int A[], int B[], int C[]) {
int i = 0, j = 0;
k = 0;
while (i < m && j < n) {
if (A[i] <= B[j]) {
C[k] = A[i];
i++;
}
else
{
C[k] = B[j];
j++;
}
k++;
}
if (i < m) {
for (int p = i; p < m; p++) {
C[k] = A[p];
k++;
}
}
else
{
for (int p = j; p < n; p++) {
C[k] = B[p];
k++;
}
}
}
// ham main
void main() {
int A[max],B[max],C[max],n,m,k;
clrscr();
cout<<"\n Nhap so phan tu cua day A: n = ";
cin>>n;
cout<<"\n Nhap so phan tu cua day B: m = ";
cin>>m;
cout<<"Nhap day A:\n";
NhapMang(A,m);
cout<<"Nhap day B:\n";
NhapMang(B,n);
cout<<"\n => Sap xep tron 2 mang A, B \n";
MergeSort(m,n,k,A,B,C);
XuatMang(C,k);
getch();
}
//==============================
[Tải Code Chương trình tại đây (Lưu ý: Sau 5s, click Bỏ qua quảng cáo - Skin Ad)]Xem thêm các thuật toán sắp xếp khác

>>> clip hướng dẫn và demo

---------------------------------------------
Xem thêm các thuật toán khác: 
1. Thuật toán tìm kiếm tuần tự
2. Thuật toán tìm kiếm nhị phân
3. Thuật toán sắp xếp đổi trực tiếp - Select sort
4. Thuật toán sắp xếp nổi bọt - Bubble sort
5. Thuật toán sắp xếp chèn trực tiếp - Insert sort
6. Thuật toán sắp xếp nhanh - Quick sort
7. Thuật toán sắp xếp hòa trộn - Merge sort
8. Thuật toán sắp xếp vun đống - Heap sort
9. Thuật toán sắp xếp shell - shell sort

2 nhận xét:

  1. cho em hỏi là sao phần tử của A là n mà lại NhapMang(A,m) là sao ạ? có nhầm lẫn gì k?

    Trả lờiXóa
  2. m là số phần tử của mảng B bạn ah.

    Trả lờiXóa

Cảm ơn bạn đã quan tâm tới bài viết này!