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.
Cài đặt thuật toán:
#include<math.h>
#include<iostream>
#include<conio.h>
#define max 100
using namespace std;
//Nhập mảng
void NhapMang(int A[],int n){
for(int i=0; i<n; i++) {
cout<<"nhap Phan tu thu A["<<i<<"] =";
cin>>A[i];
}
}
//Xuất mảng
void XuatMang(int A[],int n){
cout<<endl;
for(int i=0; i<n; i++)
cout<<A[i]<<"\t";
}
//Hoán vị 2 phần tử
void Swap(int &a,int &b){
int temp = a;
a = b;
b = temp;
}
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++;
}
}
}
//Chương trình chính
int main(){
int A[max],B[max],C[max],n,m,k;
cout<<"m = "; cin>>m;
cout<<"n = "; cin>>n;
cout<<"Nhap danh sach co thu tu A:\n";
NhapMang(A,m);
cout<<"Nhap danh sach co thu tu B:\n";
NhapMang(B,n);
cout<<"\nSap xep tron 2 mang A, B\n";
MergeSort(m,n,k,A,B,C);
XuatMang(C,k);
getch();
return 0;
}
Kết quả chạy chương trình:
Từ khóa: Sắp xếp, thuật toán, chèn, insert, insertion sort, sắp xếp chèn, giải thuật, cấu trúc dữ liệu và giải thuật, sắp xếp nhanh, quick sort, sắp xếp vun đống, heap sort, merge sort
C - C Plus Plus
Cấu trúc Dữ liệu - Giải thuật
Kỹ thuật lập trình
Code C/C++: Thuật toán sắp xếp trộn (Merge Sort)
Subscribe to:
Post Comments (Atom)
Nhãn liên kết
An toàn thông tin
Android
ASP.NET
C - C Plus Plus
C#
Cài đặt - Cấu hình
Cấu trúc Dữ liệu - Giải thuật
Chữ ký số
CodeIgniter
Đồ họa máy tính
Hệ điều hành mã nguồn mở
HTML/CSS
iOS
Java
JavaScript
Kinh nghiệm
Kỹ thuật đồ họa
Kỹ thuật lập trình
Lập trình căn bản
Lập trình hướng đối tượng
Lập trình mạng
Lập trình Mobile
Lập trình Shell
Mật mã học
Microsoft Technology
MS Access
MySQL
Pascal
PHP
PHP Framework
SQL Server
Test
Thiết kế Website
Toán cao cấp
Ubuntu/Fedora/RedHat
VB-VB.NET
Visual Studio 2015
Visual Studio 2017
Windows Form
Windows Phone
