Chơng 2 Sắp xếp trên bộ nhớ ngoài
2.4. Trộn nhiều giai đoạn
Phơng pháp sắp xếp kiểu trộn nhiều đờng cân bằng có u điểm là đơn giản và đồng đều với mọi lợt sắp xếp. Nhng nó đã hạn chế việc sử dụng cao hơn nửa số lợng băng từ hiện có để làm băng input. Phơng pháp trộn nhiều giai đoạn do R.L Gilstar đa ra năm 1960 đã khắc phục đợc nhợc điểm này. Phơng pháp này sử dụng băng từ đến mức tối đa. ở đây, nếu có n băng từ thì ta sử dụng (n - 1) băng từ làm băng input và một băng làm băng output. Nh vậy là có thể áp dụng phơng pháp trộn (n - 1) đờng chứ không phải chỉ là [n/2] đờng.
Đầu tiên các khối trên các băng input sẽ đợc trộn thành khối mới và đợc ghi vào băng output. Quá trình này tiếp tục cho tới khi một băng input cạn, lúc này băng đã cạn trở thành băng output và băng output trớc sẽ trở thành băng input, cùng với các băng input cũ để thực hiện tiếp quá trình trộn. Nh vậy rõ ràng
để phép trộn đợc thực hiện “Nhịp nhàng” lúc nào cũng có (n - 1) băng input và một băng output thì việc phân bố các khối trên băng input lúc khởi tạo không thể tuỳ tiện. Xét một vài ví dụ minh hoạ cho phơng pháp này và để từ đó chúng ta đa ra quy tắc phân phối các khối cho hợp lý.
Ví dụ 2.5: Sắp xếp băng F chứa các mẫu tin gồm 25 khoá nh sau:
F: A S O R T I N G A N D M E R G I N G E X A M P L E
Nhng với giả thiết chúng ta chỉ có ba băng F1, F2, F3 và ban đầu các khối đợc sắp xếp trên các băng nh sau:
F1: A O R S T I N A G N D E M R G I N F2: E G X A M P E L
F3:
Băng F3 đợc khởi tạo lúc đầu và là băng xuất dành cho lần trộn đầu. Trộn lần lợt 3 khối đầu của băng F1 với 3 khối đầu của băng F2 theo phơng pháp trộn hai đờng để tạo thành 3 khối mới (có thứ tự trong mỗi khối) ghi vào băng F3, bây giờ băng F2 trở thành rỗng:
F1: D E M R G I N F2:
F3: A E G O R S T X A I M N P A E G L N
Tiếp tục trộn lần lợt 2 khối của băng F1 với 2 khối đầu của băng F3 theo phơng pháp trộn hai đờng để tạo thành 2 khối mới ghi vào băng F2 và lúc này băng F1 rỗng:
F1:
F2: A D E E G M O R R S T X A G I I M N N P F3: A E G L N
Một lần nữa trộn khối đầu tiên của băng F2 với khối của băng F3 để tạo thành khối mới ghi vào băng F1 và lúc này băng F3 rỗng:
F1: A A D E E E G G L M N O R R S T X F2: A G I I M N N P
F3:
Nh vậy, bây giờ băng F1 và băng F2 mỗi băng còn 1 khối. Ta thực hiện trộn 2 khối trên 2 băng này để tạo thành một khối duy nhất và ghi lên băng F3:
F1: F2:
F3: A A A D E E E G G G I I L M M N N N O P R R S T X
Đến đây, các khoá đã đợc sắp thứ tự và quá trình trộn kết thúc. Có thể đợc mô tả nh hình 2.1.
Ví dụ 2.6: Cũng trộn nhiều giai đoạn với 3 băng F1, F2, F3 nhng số lợng các khối là nhiều hơn và phân bố trên các băng là khác so với ví dụ 2.5.
Giả sử lúc đầu băng F1 và băng F2 chứa lần lợt 13 khối và 8 khối. Thế thì
trong lợt đầu 8 khối của F2 trộn với 8 khối của F1 (trên băng F1 sẽ còn lại 5 khối)
để thành 8 khối mới, ghi vào F3. ở lợt thứ hai 5 khối của F2 trộn với 5 khối của F3
(trên băng F3 sẽ còn lại 3 khối) để thành 5 khối mới, ghi vào F2. ở lợt thứ ba 3 khối của F3 trộn với 3 khối của F2 (trên băng F2 sẽ còn lại 2 khối) để thành 3 khối mới, ghi vào F1 ... Cuối cùng ta sẽ đợc một khối lớn ứng với tệp. Minh hoạ ở hình 2.2.
F1 F2 F3 F1 F2 F3
5 3 13 8
2 0 3 5 0 8
0 2 1 0 5 3
1 1 0 3 2 0
0 0 1 1 0 2 H×nh 2.1
0 1 1
1 0 0
H×nh 2.2
Ví dụ 2.7: Minh hoạ phơng pháp trộn nhiều giai đoạn với 6 băng F1, F2, F3, F4, F5, F6. Đầu tiên F1 có 16 khối, F2 có 15 khối, F3 có 14 khối, F4 có 12 khối, F5
có 8 khối, F6 là rỗng
Bớc đầu, 8 khối đợc trộn vào F6, khi này F5 rỗng. Tiếp tục trộn...và ta đợc sơ đồ minh hoạ nh hình 2.3.
F1 F2 F3 F4 F5 F6
16 15 14 12 8
8 7 6 4 0 8
4 3 2 0 4 4
2 1 0 2 2 2
1 0 1 1 1 1
0 1 0 0 0 0
H×nh 2.3.
Trộn nhiều giai đoạn hiệu quả hơn trộn nhiều đờng cân bằng vì với N băng ta luôn dùng phép trộn (N - 1) đờng thay vì [N/2] đờng. Vì số bớc cần thiết khoảng logNn, với n là số khoá cần sắp và N là bậc những phép toán trộn.
Dĩ nhiên, sự phân bố các khối ban đầu trong các ví dụ trên đã đợc lựa chọn cẩn thận. Để tìm đợc sự phân bố tốt cho các đờng ban đầu, chúng ta làm ngợc lại.
Bắt đầu với sự phân bố cuối cùng. Lập lại 2 bảng ở ví dụ 2.6 và ví dụ 2.7, xoay mỗi dòng một vị trí đối với dòng trớc nó, chúng ta có 2 bảng với 6 bớc 3 băng và 6 bíc 6 b¨ng:
Bảng 1: phân bố các khối lên 2 băng l a1(l) a2(l) Σai(l)
0 1 0 1
1 1 1 2
2 2 1 3
4 5 3 8
5 8 5 13
6 13 8 21
Bảng 2: Phân bố các khối lên 5 băng
l a1(l) a2(l) a3(l) a4(l) a5(l) Σai(l)
0 1 0 0 0 0 1
1 1 1 1 1 1 5
2 2 2 2 2 1 9
3 4 4 4 3 2 17
4 8 8 7 6 4 33
5 16 15 14 12 8 65
+)Từ bảng 1, suy ra các phơng trình:
a2(l+1) = a1(l)
a1(l+1) = a1(l) + a1(l) víi l > 0 và a1(0) = 1, a2(0) = 0.
Xem a1(l) là fi+1 ta có:
fi+1 = fi + fi-1 víi i ≥ 1 f1 = 1
f0 = 0
Đó là định nghĩa đệ quy của dãy Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,...
Mỗi số Fibonacci là tổng của 2 số đứng trớc nó. Nh thế số các khối ban
đầu trên 2 băng phải có 2 số Fibonacci để phơng pháp sắp xếp trộn nhiều giai
đoạn hoạt động tốt hơn.
+) Từ bảng 2, suy ra các phơng trình:
a5(l+1) = a1(l)
a4(l+1) = a1(l) + a5(l) = a1(l) + a1(l-1)
a3(l+1) = a1(l) + a4(l) = a1(l) + a1(l-1) + a1(l-2)
a2(l+1) = a1(l) + a3(l)= a1(l)+ a1(l-1)+ a1(l-2)+a1(l-3)
a1(l+1) = a1(l)+a2(l) = a1(l) + a1(l-1) + a1(l-2) + a1(l-3) + a1(l-4)
Thay a1(l) = fi và a1(0) = 1, a2(0) = a3(0) = a4(0) = a5(0) = 0 Ta cã:
fi+1 = fi + fi-1 + fi-2 + fi-3 + fi-4 víi i ≥ 4 f4 = 1
fi = 0 víi 0 ≤ i < 4.
Đây là các số Fibonacci.
Một cách tổng quát, dãy Fibonacci bậc p đợc định nghĩa nh sau:
fi+1(P ) = fi(P ) + fi-1(P ) +....+ fi-P(P ) víi i ≥ P fP(P ) = 1
fi(P ) = 0 víi 0 ≤ i < P
Nh vậy các số Fibonacci mà ta đã biết trớc đây chính là các số Fibonacci cấp 1. Bây giờ chúng ta đã biết số ban đầu các khối để cho thuật giải sắp nhiều giai đoạn đợc hoạt động hoàn hảo, với n băng là tổng bất kỳ (n - 1), (n - 2), ..., 1 các số kế nhau của dãy Fibonacci bậc (n - 2). Nghĩa là tổng các khối ban đầu phải là: S(l)n = ∑−
= 1 1
) n ( i
l
Mi
Sau đây là bảng giá trị Sn(l) ứng với một số giá trị cụ thể của m và l:
l n 3 4 5 6 7 8
1 2 3 4 5 6 7
2 3 5 7 9 11 13
3 5 9 13 17 21 25
4 8 17 25 33 41 49
6 21 57 94 129 161 193
7 34 105 181 253 321 385
8 55 193 349 497 636 769
9 89 355 673 977 1261 1531
10 144 653 1297 1921 2501 3049
11 233 1201 2500 3777 4961 6073
12 377 2209 4819 7425 9841 12097
13 610 4063 9289 14597 19521 24097
14 987 7473 17905 28697 38721 48001
15 1597 13745 34513 56417 76806 95617
16 2584 25281 66526 110913 152351 190465 17 4181 46499 128233 218049 302201 379399 18 6765 85525 247177 428673 599441 755749 19 10946 57305 476449 842749 1189041 1505425 20 17711 289329 918385 1656801 2358561 2998753
Tuy nhiên, những điều nói trên rõ ràng là chỉ phù hợp với trờng hợp mà tổng số các khối hiện có đúng bằng Sn(l). Còn với trờng hợp mà số các khối ban
đầu không bằng đúng các tổng “Lý tởng ” đó thì sao? Ta có thể nghĩ rằng ta sẽ thay các khối thiếu hụt bằng các khối rỗng, nghĩa là các khối giả. Nhng nếu nh vậy thì làm sao có thể biết đợc các khối giả trong quá trình trộn? Vấn đề này rất quan trọng. Nếu nh ta biết trên băng Fi có khối giả thì khi trộn ta vẫn coi nh nó có tham dự, nhng nếu nh không biết thì ta có thể nhầm tởng là băng từ đó đã cạn và sẽ cho nó chuyển quá sớm thành băng output; điều đó sẽ làm cho trộn nhiều giai đoạn thực hiện lệch lạc không đúng nh dự kiến nữa.
Việc khắc phục những nhợc điểm này là quá khó nên trong chơng này sẽ tạm thời không đi sâu vào nữa.