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 [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:
------------------------
Tự học lập trình C++:
------------------------
Bài 1: Chương trình đầu tay
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++
Chúc các bạn thành công!
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]
* Có thể bạn quan tâm:
- Những cuốn sách mà các bạn không thể bỏ qua khi còn trẻ
- Khoá học tin học văn phòng tốt nhất
Chúc các bạn thành công!