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

in , , , , , , , /

 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:
Thuật toán Merge-Sort

+ 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();
}
//==============================


--------------------------------------------
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

------------------------
Tự học lập trình C++:

------------------------

Bài 1: Chương trình đầu tay
Bài 2: Các kiểu dữ liệu cơ bản chuần trong C\C++
Bài 3: Nhập, Xuất trong C/C++
Bài 4: Cấu trúc rẽ nhánh (IF)
Bài 5: Cấu trúc lặp for
Bài 6: Cấu trúc lặp while
Bài 7: Cấu trúc lặp do ... while
Bài 8: Cấu trúc lựa chọn switch... case
Bài 9: Dữ liệu kiểu mảng (array)
Bài 10: Dữ liệu kiểu cấu trúc (struct)
Bài 11: Hàm (function)
Bài 12: Dữ liệu kiểu con trỏ (pointer)
Bài 13: Xử lý tệp tin (file)
Bài 14: Lập trình hướng đối tượng (OOP) với C++


Một số tài liệu và khoá học bổ ích dành cho bạn: 

# Giáo Trình: Kỹ Thuật Lập Trình C/C++ Căn Bản Và Nâng Cao [Click để xem]

# Khoá học online: Học lập trình C/C++ TỪ A - Z [Click để xem]



Chúc các bạn thành công!