Thuật toán Merge-Sort

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

#include <iostream>
#include <conio.h>
using namespace std;
#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
int 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();
 return 0;
}