Trở về đầu
Mời các bạn download tại: Click here
#include <iostream>
using namespace std;
int n,m,k;
int a[1000], a2[1000];
void Nhap() {
cout << "Nhap vao so phan tu cua mang a la: ";
cin >> n;
cout << "Nhap vao cac phan tu cua mang a: ";
for (int i = 1; i <= n; i++){
cin >> a[i];
}
}
void Merge(int * x, int * y, int a, int b, int c) {
// Trong 2 mang x[a..b] va x[b+1..c] thanh mang y[a..c] tang dan
int csbna = a;
int csbnb = b+1;
for (int i=a; i<=c; i++){
if (csbna > b) { // Mang a het phan tu
for (int k=i; k<=c; k++) {
y[k] = x[csbnb];
csbnb++;
}
return;
}
if (csbnb > c){
for (int k=i;k<=c;k++){
y[k] = x[csbna];
csbna++;
}
return;
}
if (x[csbna] < x[csbnb]) {
y[i] = x[csbna];
csbna++;
}
else{
y[i] = x[csbnb];
csbnb++;
}
}
}
void MergeByLength(int * x, int * y, int len) {
int a = 1;
int b = len;
int c = 2*len;
while (c <= n) {
Merge(x, y, a, b, c);
a = a + 2*len;
b = b + 2*len;
c = c + 2*len;
}
if (b < n) { // Con 2 mach
// - Mach thu nhat co len phan tu tu [a..b]
// - Mach thu hai co n - b phan tu
Merge(x, y, a, b, n);
}
else // b >= n, nghia la n <= b: Con 1 mach: [a..n]
for (int k = a; k<=n; k++) y[k] = x[k];
}
void MergeSort() {
bool Flag = true;
int len = 1;
while (len < n) {
if (Flag == true) MergeByLength(a, a2, len);
else MergeByLength(a2, a, len);
len = 2*len;
Flag = !Flag;
}
if (Flag == false) {
for (int i=1; i<=n; i++) a[i] = a2[i];
}
}
void InKetQua() {
for(int i=1; i<=n; i++)
cout << a[i] << " ";
}
int main(){
Nhap();
MergeSort();
InKetQua();
return 0;
}