Cho dãy X = {X1, X1, ..., Xn}, hãy sắp xếp dãy theo chiều không giảm.
2. Ý tưởng
- Giả sử dãy X[1],...,X[i],...,X[n] có hai đoạn đã được sắp xếp không giảm là X[1],...,X[i] và X[i+1],...,X[n], ta tiến hành tạo ra dãy mới bằng cách lần lượt lấy hai phần tử đầu tiên của mỗi đoạn và so sánh với nhau. Phần tử nào nhỏ hơn thì lấy ra dãy mới và bỏ nó ra khỏi đoạn đang xét. Cứ tiến hành như vậy cho tới khi một dãy bị vét hết (không còn phần tử nào). Lấy toàn bộ phần tử còn lại của đoạn không xét hết nối vào sau dãy đích. Như vậy dãy mới là một dãy đã được sắp xếp.
- Trong mọi trường hợp, có thể coi dãy gồm duy nhất 1 phần tử là đã được sắp xếp. Lợi dụng việc này, ta phân chia một dãy ra thành nhiều dãy con chỉ gồm một phần tử rồi lần lượt hòa nhập từng đôi một với nhau.
Thuật toán viết bằng C++ :
void Merge(int a[], int k1, int k2, int k3)
{
int i,j,k,t;
int temp[];
i=k1; j=k2; k=k3;
while (i<k2) and (j<=k3)
{
if (a[i]<=a[j]){
temmp[k]=a[i];
i=i+1;
}
else{
temp[k]=a[j];
j=j+1;
}
k=k+1;
}
if (i>=k2)
for(t=j;t<=k3,t++)
temp[k+t-j]=a[t];
else
for(t=i;t<=k2,t++)
temp[k+t-i]=a[t];
for(k=k1;t<=k3,k++)
a[k]=temp[k];
}
Code:
// Thủ tục trộn gọi đệ quy
void MergeSort(int X[], int L, int R)
{
int M;
if (L<R){
M=int((L+R)/2);
MergeSort(X,L,M);
MergeSort(X,M+1,R);
Merge(X,L,M+1,R);
}
}
// Thủ tục trộn hai đoạn đã sắp xếp trong một dãy// Thủ tục trộn gọi đệ quy
void MergeSort(int X[], int L, int R)
{
int M;
if (L<R){
M=int((L+R)/2);
MergeSort(X,L,M);
MergeSort(X,M+1,R);
Merge(X,L,M+1,R);
}
}
void Merge(int a[], int k1, int k2, int k3)
{
int i,j,k,t;
int temp[];
i=k1; j=k2; k=k3;
while (i<k2) and (j<=k3)
{
if (a[i]<=a[j]){
temmp[k]=a[i];
i=i+1;
}
else{
temp[k]=a[j];
j=j+1;
}
k=k+1;
}
if (i>=k2)
for(t=j;t<=k3,t++)
temp[k+t-j]=a[t];
else
for(t=i;t<=k2,t++)
temp[k+t-i]=a[t];
for(k=k1;t<=k3,k++)
a[k]=temp[k];
}