Kênh Tên Miền chuyên cung cấp tên miền đẹp, giá rẻ! Hãy liên hệ kỹ thuật: 0914205579 - Kinh doanh: 0912191357 để được tư vấn, hướng dẫn miễn phí, Cảm ơn quý khách đã ủng hộ trong thời gian qua!
Sunday, April 5, 2015



Giải thuật Merge sort sắp xếp dãy a1, a2, ..., an dựa trên nhận xét sau:
Mỗi dãy a1, a2, ..., an bất kỳ là một tập hợp các dãy con liên tiếp mà mỗi dãy con đều đã có thứ tự.
Ví dụ: dãy 12, 2, 8, 5, 1, 6, 4, 15 có thể coi như gồm 5 dãy con không giảm (12); (2, 8); (5); (1, 6); (4, 15).
Dãy đã có thứ tự coi như có 1 dãy con.
Hướng tiếp cận: tìm cách làm giảm số dãy con không giảm của dãy ban đầu.
Bước 1 : // Chuẩn bị
k = 1; // k là chiều dài của dãy con trong bước hiện hành
Bước 2 :
Tách dãy a0, a1, ., an-1 thành 2 dãy b, c theo nguyên tắc luân phiên từng nhóm k phần tử:
b = a0, ., ak, a2k, ., a3k, .
c = ak+1, ., a2k+1, a3k+1, .
Bước 3 :
Trộn từng cặp dãy con gồm k phần tử của 2 dãy b, c vào a.
Bước 4 :
k = k*2;
Nếu k < n thì trở lại bước 2.
Ngược lại: Dừng
Dữ liệu hỗ trợ: 2 mảng b, c:
int  b[MAX], c[MAX], nb, nc;
Các hàm cần cài đặt:
void MergeSort(int a[], int N); : Sắp xếp mảng (a, N) tăng dần
void Distribute(int a[], int N, int &nb, int &nc, int k); Phân phối đều luân phiên các dãy con độ dài k từ mảng a vào hai mảng con b và c
void Merge(int a[], int nb, int nc, int k); : Trộn mảng b và mảng c vào mảng a
void MergeSubarr(int a[], int nb, int nc, int &pa, int &pb, int &pc, int k); : Trộn một cặp dãy con từ b và c vào a


int b[MAX], c[MAX], nb, nc;

void MergeSort(int a[], int N)
{
int k;
for (k = 1; k < N; k *= 2) 
{
Distribute(a, N, nb, nc, k);
Merge(a, nb, nc, k);
}
}
void Distribute(int a[], int N, int &nb, int &nc, int k)
{
int i, pa, pb, pc;
pa = pb = pc = 0;
while (pa < N)
{
for (i=0; (pa<N) && (i<k); i++, pa++, pb++)
b[pb] = a[pa];
for (i=0; (pa<N) && (i<k); i++, pa++, pc++)
c[pc] = a[pa];
}
nb = pb; nc = pc;
}
void Merge(int a[],int nb, int nc,int k)
{ int p, pb, pc, ib, ic, kb, kc;
p=pb=pc=0; ib=ic=0;
while((nb>0)&&(nc>0))
{ kb=min(k,nb); kc=min(k,nc);
if(b[pb+ib]<=c[pc+ic])
{ a[p++]=b[pb+ib]; ib++;
if(ib==kb)
{ for(;ic<kc;ic++ a[p++]=c[pc+ic];
pb+=kb; pc+=kc; ib = ic=0;
nb-=kb; nc-=kc;
}
}  
else
{ a[p++]=c[pc+ic]; ic++;
if(ic==kc)
{
for(;ib<kb;ib++) a[p++]=b[pb+ib];
pb+=kb;  pc+=kc; ib = ic=0;
nb-=kb; nc-=kc;
}
}
}
}
int min(int a,int b)
{
if(a>b) return b;
else return a;
}

0 comments:

Post a Comment

Popular Posts