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 26, 2015

 Phương pháp trộn Run
Khái niệm cơ bản:
 Run là một dãy liên tiếp các phần tử được sắp thứ tự. Ví dụ 2  4  7  12  50 là một run gồm có 5 phần tử
 Chiều dài run chính là số phần tử trong Run. Chẳng hạn, run trong ví dụ trên có chiều dài là 5.
 7 8 5 3 9 12 4 23 78 90 45 54


Giải thuật: Giải thuật sắp xếp tập tin bằng phương pháp trộn run có thể tóm lược như sau: Input: f0 là tập tin cần sắp thứ tự. Output: f0 là tập tin đã được sắp thứ tự. Gọi f1, f2 là 2 tập tin trộn. Các tập tin f0, f1, f2 có thể là các tập tin tuần tự (text file) hay có thể là các tập tin nhị phân.

 Bước 1:
 - Giả sử các phần tử trên f0 là:  24 12 67 33 58 42 11 34 29 31
 - Khởi tạo f1, f2 rỗng
 - Thực hiện phân bố m=1 phần tử lần lượt từ f0 vào f1 và f2:
 f1: 24 67 58 11 29 f2: 12 33 42 34 31
 Trộn f1, f2 thành f0:
 f0: 12 24 33 67 42 58 11 34 29 31

 Bước 2:
 -Phân bố m=2 phần tử lần lượt từ f0 vào f1 và f2:
 f1: 12 24 42 58 29 31
f0: 12 24 33 67 42 58 11 34 29 31
f2: 33 67 11 34
- Trộn f1, f2 thành f0: f1: 12 24 42 58 29 31 f0: 12 24 33 67 11 34 42 58 29 31 f2: 33 67 11 34

Bước 3: - Tương tự bước 2, phân bố m=4 phần tử lần lượt từ f0 vào f1 và f2, kết quả thu được như sau: f1: 12 24 33 67 29 31 f2: 11 34 42 58 - Trộn f1, f2 thành f0: f0: 11 12 24 33 34 42 58 67 29 31

Bước 4: - Phân bố m=8 phần tử lần lượt từ f0 vào f1 và  f2: f1: 11 12 24 33 34 42 58 67 f2: 29 31 - Trộn f1, f2 thành f0: f0: 11 12 24 29 31 33 34 42 58 67

Bước 5: Lặp lại tương tự các bước trên, cho đến khi chiều dài m của run cần phân bổ lớn hơn chiều dài n của f0 thì dừng.

void chia(FILE *a,FILE *b,FILE *c,int p) void main (void) { FILE *a,*b,*c; tao_file(); xuat_file(); p = 1; while (p < n) { chia(a,b,c,p); tron(b,c,a,p); p=2*p; } }

void chia(FILE *a,FILE *b,FILE *c,int p) while (!feof(a)) { /*Chia p phan tu cho b*/ dem=0; while ((dem<p) && (!feof(a))) { fscanf(a,"%3d",&x); fprintf(b,"%3d",x); dem++; }

 dem=0; while ((dem<p) && (!feof(a))) { fscanf(a,"%3d",&x); fprintf(c,"%3d",x); dem++; } }
 void tron(FILE *b,FILE *c,FILE *a,int p) int stop,x,y,l,r; a=fopen("d:\ctdl\sortfile\bang.int","wb"); b=fopen("d:\ctdl\sortfile\bang1.int","rb"); c=fopen("d:\ctdl\sortfile\bang2.int","rb"); while ((!feof(b)) && (!feof(c))) { l=0;/*so phan tu cua b da ghi len a*/ r=0;/*so phan tu cua c da ghi len a*/ fscanf(b,"%3d",&x); fscanf(c,"%3d",&y); stop=0;

while ((l!=p) && (r!=p) && (!stop)) { if (x<y) { fprintf(a,"%3d",x); l++; if ((l<p) && (!feof(b))) /*chua du p phan tu va chua het file b*/ fscanf(b,"%3d",&x); else { fprintf(a,"%3d",y); r++; if (feof(b)) stop=1; } }

else
{
fprintf(a,"%3d",y); r++; if ((r<p) && (!feof(c))) /*chua du p phan tu va chua het file c*/ fscanf(c,"%3d",&y); else {

fprintf(a,"%3d",x); l++; if (feof(c)) stop=1; } } } //Chep phan con lai cua p phan tu tren b len a
while ((!feof(b)) && (l<p)) { fscanf(b,"%3d",&x); fprintf(a,"%3d",x); l++; }

//Chep phan con lai cua p phan tu tren c len a while ((!feof(c)) && (r<p)) { fscanf(c,"%3d",&y); fprintf(a,"%3d",y); r++; } } if (!feof(b)) { /*chep phan con lai cua b len a*/ while (!feof(b)) { fscanf(b,"%3d",&x); fprintf(a,"%3d",x); } }

{
fscanf(c,"%3d",&x); fprintf(a,"%3d",x);
} } fclose(a);  fclose(b);  fclose(c); }

 /*Chia p phan tu cho c*/ dem=0; while ((dem<p) && (!feof(a))) { fscanf(a,"%3d",&x); fprintf(c,"%3d",x); dem++; } }

0 comments:

Post a Comment

Popular Posts