Luận văn tốt nghiệp

Một số ph ơng pháp sắp xếp và tìm kiếm ngoài
Mục lục
Trang

Lời nói đầu

2

Chơng 1. Mô hình của xử lý ngoài

3

1.1. Tập tin

4

1.2. Lu trữ hai cấp

4

1.3. Mẫu tin bị chốt

5

1.4. Tổ chức của mẫu tin

6

1.5. Mẫu tin có chiều dài thay đổi


2.6. Những nhận xét chung

31

Chơng 3. Tìm kiếm trên bộ nhớ ngoài

33

3.1. File tuần tin

34

3.2. File băm

36

3.3. File có chỉ số

39

3.4. Cây tìm kiếm ngoài

44

3.4.1. Cây tìm kiếm đa nhánh

44

3.4.2. B-Cây

nhân khoa học, tôi mạnh dạn chọn đề tài: "Một số phơng pháp sắp xếp và tìm
kiếm trên bộ nhớ ngoài".
Luận văn đợc chia thành 3 chơng.
Chơng 1: "Mô hình của xử lý ngoài", bàn luận về các kỹ thuật lu trữ vật lý.
Chơng 2: "Sắp xếp trên bộ nhớ ngoài", giới thiệu chi tiết về các phơng
pháp để sắp xếp lại các tập tin theo thứ tự; một loạt các phơng pháp sẽ đợc phát
triển, đợc mô tả và đợc so sánh với nhau.
Chơng 3: "Tìm kiếm trên bộ nhớ ngoài", giới thiệu chi tiết về các phơng
pháp cơ bản và nâng cao để thực hiện công việc tìm kiếm.
Để hoàn thành Luận văn, tôi đã nhận đợc sự hớng dẫn nhiệt tình của Thầy
giáo Trần Xuân Hào. Nhân dịp này cho phép tôi bày tỏ lòng biết ơn sâu sắc đến
Thầy giáo. Đồng thời tôi xin chân thành cảm ơn các Thầy giáo, Cô giáo thuộc tổ
"Tin học đại cơng và phơng pháp giảng dạy" đã động viên giúp đỡ tôi nhiều trong
quá trình học tập, rèn luyện và thực hiện đề tài. Tuy nhiên, vì thời gian có hạn và
năng lực còn non nớt nên Luận văn chắc không tránh khỏi những sai sót. Rất
mong đợc sự góp ý quý báu từ phía Thầy giáo, Cô giáo và bạn bè.
Tác giả

2


Luận văn tốt nghiệp

Một số ph ơng pháp sắp xếp và tìm kiếm ngoài

Chơng 1

mô hình của xử lý ngoài

Các cấu trúc dữ liệu mà chúng ta xét trớc đây đều giả thiết rằng các dữ liệu

trỏ chỉ đến đối tợng đó (nghĩa là những con trỏ chỉ đến mẫu tin biểu diễn đối tợng này).

1.1. Tập tin
Giống nh các mô hình dữ liệu cấp cao, các mẫu tin thờng đợc xem là
những thể hiện của một lợc đồ. Nghĩa là chúng ta phải xử lý tập các mẫu tin có
cùng số lợng trờng, và các trờng tơng ứng có cùng kiểu dữ liệu, cùng tên và cùng
ý nghĩa. Chẳng hạn các mẫu tin biểu diễn các bộ của một quan hệ của một trờng
cho mỗi thuộc tính của quan hệ đó. Chúng ta hãy gọi danh sách các tên trờng và
kiểu dữ liệu tơng ứng là khuôn dạng cho mẫu tin.
Chúng ta dùng thuật ngữ tập tin để biểu thị một tập các mẫu tin có cùng
khuôn dạng. Vì vậy tập tin là một cách biểu diễn vật lý thích hợp cho một quan
hệ. Khái niệm tập tin theo cách này khác với khái niệm thông thờng của một
Tập tin, đó là một Dòng các chuỗi ký tự, hoặc có thể thuộc kiểu cơ bản khác,
và chỉ truy xuất đợc nó bằng cách Quét từ đầu đến cuối. Trong chơng 2 và chơng 3 chúng ta sẽ thấy rằng có nhiều cách khác nhau để truy xuất các tập tin, và
những mẫu tin thờng không đợc lu trữ theo kiểu một Dòng dữ liệu.

1.2. Lu trữ hai cấp
Thiết bị lu trữ tin vật lý dùng để ghi các mẫu tin và các tập tin có thể xem
nh một mảng các byte đợc đánh số tuần tự. Chẳng hạn thiết bị lu trữ tin có thể là
vùng nhớ ảo có các byte đợc đánh số từ 0 đến một số rất lớn, có thể lên đến 2 24
hoặc 230. Bộ nhớ ảo này có thể đợc lu trữ trên bộ nhớ thứ cấp hay còn gọi là bộ
nhớ phụ, chẳng hạn nh các băng từ, đĩa từ. Các thiết bị này có đặc điểm truy nhập
hoàn toàn khác với bộ nhớ trong. Chẳng hạn, với băng từ: Dữ liệu sẽ đợc ghi
nhận trên băng dọc theo chiều dài của nó, chúng đợc đọc ghi bởi đầu từ. Khi có
lệnh đọc ghi, băng từ đợc kéo chạy qua đầu từ. Nh vậy sẽ phải xuất các đoạn

4


Luận văn tốt nghiệp


5


Luận văn tốt nghiệp

Một số ph ơng pháp sắp xếp và tìm kiếm ngoài

một thời điểm nào đó chúng ta xoá r, và về sau lại đặt một mẫu tin r vào vị trí trớc đó của r. Khi đó nếu đi theo con trỏ p, chúng ta có thể thấy mẫu tin r ở vị trí r,
không có dấu vết nào cho thấy mẫu tin chúng ta vừa tìm đợc không phải là mẫu
tin r do p chỉ đến. Dù có sử dụng cặp khối-khoá làm con trỏ, chúng ta vẫn không
bảo đảm an toàn trong vấn đề này, đó là vấn đề con trỏ h ảo hay tham chiếu h
ảo. Lý do là r có thể có cùng giá trị khoá nh r, vì nó đợc chèn vào trong tập tin
sau khi r đã bị loại bỏ đi, và nh thế không vi phạm giá trị khoá duy nhất.
Để tránh các con trỏ h ảo, mỗi mẫu tin cần có một bit gọi là bit Xoá, nó
đợc đặt là 1 nếu mẫu tin bị xoá. Vùng lu trữ cho mẫu tin này có thể không bao
giờ đợc dùng lại, và khi truy tìm một mẫu tin, chẳng hạn bằng cách đi theo con
trỏ, chúng ta có thể nhận ra rằng mẫu tin đã bị xoá, nghĩa là mẫu tin thực sự đã
không còn ở đó và có thể bỏ qua nó.

1.4. Tổ chức của mẫu tin
Khi sắp xếp các trờng trong một mẫu tin, chúng ta phải đặt chúng theo một
cách nào đó để có thể truy xuất đợc giá trị của chúng. Nếu tất cả các trờng có
chiều dài cố định thì chúng ta chỉ cần chọn một thứ tự cho các trờng này. Vì thế
mỗi trờng sẽ bắt đầu tại một byte nhất định nào đó đợc gọi là offset, đợc tính từ
đầu mẫu tin. Cho nên khi dò theo một mẫu tin đã biết đợc khuôn dạng của nó,
chúng ta có thể tìm ra một trờng khi biết vị trí bắt đầu của mẫu tin, bằng cách di
chuyển về phía trớc một số byte bằng với offset của trờng đó.
Cũng có thể có nhiều byte không dùng để chứa dữ liệu. Chẳng hạn chúng
ta có thể cần:

số đợc lu trong trờng NUMBER. Tất cả các số nguyên dơng đều có tên khởi đầu
bằng một trong những chữ cái của từ Soften, nhng ở đây chúng không có vai
trò quan trọng nào.
3. Trờng SQUARE giữ giá trị bình phơng của số trong trờng đầu tiên.
Trong ví dụ này SQUARE thuộc kiểu số nguyên.

7


Luận văn tốt nghiệp

Một số ph ơng pháp sắp xếp và tìm kiếm ngoài

Với giả thiết là mỗi số nguyên chiếm 4 byte, ba trờng ở trên cả thảy cần 9
byte. Chúng ta cũng thêm một byte ở đầu mỗi mẫu tin. Byte này chứa bit Đã
dùng/ cha dùng và bit "Xoá". Chúng ta gọi byte này là INFO.
0

1

2

3

4

7
NUMBER

8


thờng cho các chuỗi ký tự có chiều dài thay đổi. Các trờng và các byte thông tin
của mẫu tin nh sau:
1. Byte 0 chứa chiều dài của toàn bộ mẫu tin, bao gồm luôn trờng thay đổi.
Vì vậy giới hạn cho SQUARE thờng không phải là 255 byte bởi vì toàn bộ mẫu
tin không đợc vợt quá 255 byte.
2. Byte 1 giữ các bit INFO nh ở ví dụ 1.1.
3. Byte 2 giữ trờng NAME.
4. Byte 3 bỏ trống.
5

5. Byte 4 - 7 giữ trờng NUMBER.
6. Byte 8 giữ chiều dài của trờng SQUARE.
7. Từ byte 9 trở đi lu các giá trị của SQUARE dới dạng chuỗi ký tự
Nội dung của hai mẫu tin cho hai số 2 và 13 đợc trình bày nh hình 1.2.
Chú ý rằng vì chỉ có một trờng thay đổi nên chiều dài của mẫu tin và chiều
dài của trờng đó rất dễ liên hệ, do đó chúng ta có thể bỏ đi byte 0 và byte 8 nhng
không đợc đồng thời bỏ cả hai byte này. Nghĩa là giá trị của byte 0 luôn lớn hơn
giá trị của byte 8 là 9 byte.
Chúng ta cũng cần nhớ rằng trong khuôn dạng này, nếu có những trờng đi
sau SQUARE thì chúng ta phải nhờ đến byte 8 để tìm ra chúng. Chẳng hạn về lý
thuyết, offset của trờng đi theo sau SQUARE phải bằng 9 cộng thêm nội dung
của byte 8.
0
10

INFO

1



INFO

1

Một số ph ơng pháp sắp xếp và tìm kiếm ngoài
2

3

4

t

7

8

9

10

11

13

3

1



Luận văn tốt nghiệp

Một số ph ơng pháp sắp xếp và tìm kiếm ngoài

Chơng 2

Sắp xếp trên bộ nhớ ngoài

Phần lớn các phơng pháp sắp xếp ngoài sử dụng chiến lợc tổng quát:
Tạo một lần duyệt trên tập tin cần sắp, chia nó thành các khối có kích thớc phù
hợp và sắp xếp các khối này. Sau đó trộn các khối này với nhau bằng cách duyệt
vài lần tập tin, rồi lại tạo các khối đợc sắp lớn hơn cho đến khi sắp xong toàn bộ
tập tin. Đa số dữ liệu thờng đợc truy xuất theo kiểu tuần tự, đây là tính chất làm
cho phơng pháp này thích hợp đối với các thiết bị bên ngoài.

2.1. Phơng pháp trộn trực tiếp
Phơng pháp chung: Cho trớc băng F chứa tập tin gồm n khóa
Bớc 1: Chia đôi băng F thành 2 băng F 1 và F2 bằng cách sao [n/2] khoá lên
băng F1 và phần còn lại lên F2. Trộn lần lợt các khối một khoá của băng F1 và các
khối một khoá tơng ứng của băng F2 để tạo ra các khối có thứ tự ghi vào băng F.
Bớc 2: Sau bớc 1, băng F chứa một dãy các khối hai khoá (có thứ tự trong
mỗi băng). Một lần nữa, ta chia nó thành hai băng F 1 và F2, bằng cách sao một
nửa số khối hai khoá lên F1 và nửa còn lại lên F2.
Tiếp tục trộn lần lợt các khối hai khoá tơng ứng trong F1và F2 để tạo ra các
khối bốn khoá (có thứ tự trong mỗi khối ) ghi vào F.
Bớc 3: Lặp lại các bớc trên, trộn các khối bốn khoá thành khối tám khoá.
Rồi cứ tiếp tục, mỗi lần lại nhân đôi độ dài của khối đợc sắp, cho tới khi toàn bộ
các khoá trong băng F đợc sắp.
Tất cả các khối đợc tạo ra trong các bớc có thể có cùng kích thớc, nhng

F2: E R G I

N G A N D M

N G E X A M P L E

F: AE
Tiếp theo ta trộn khối một khoá thứ hai của F 1 với khối một khoá thứ hai
của F2 để tạo ra hai khoá có thứ tự rồi ghi vào F:
F1: A

S O R

T

I

F2: E

R

N

G E X A M P

G

I

N G


DP

LM E

MN

Tiếp tục trộn các khối tơng ứng trong F1 và F2 để tạo ra các khối bốn khoá
và ghi vào F (tệp F2 chứa một khối một khoá cuối cùng cũng đợc sao vào F ), sau
lần trộn này ta đợc:

12


Luận văn tốt nghiệp

Một số ph ơng pháp sắp xếp và tìm kiếm ngoài

F: A E E N R G S X

AAGO IMNR

DNPT

GILM E

Đến đây băng F chứa một dãy các khối bốn khoá. Lại tiếp tục chia nó
thành F1 và F2 bằng cách sao một nửa số khối lên F1 và nửa còn lại lên F2:
F1: A E E N


và ghi vào F, sau lần trộn này ta đợc:
F: A A A E E G G I I L M M N N O R

DEGNPRSTX

Băng F bây giờ chứa hai khối, tiếp tục sao khối đầu tiên vào F 1 và khối sau
vào F2:
F1: A A A E E G G I I L M M N N O R
F2: D E G N P R S T X
Trộn các khối trong F1 và F2 để tạo ra khối có 25 khoá:
F: 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
Nh vậy, các mẫu tin đã đợc sắp xếp xong.
Ví dụ 2.2: Trờng hợp các khối có kích thớc bằng nhau trong từng bớc
Sắp xếp băng F gồm 32 khoá nh sau:
F: A S O R T I N G A N D M E R G I R T I N A N G F N R E X N S T T

13


Luận văn tốt nghiệp

Một số ph ơng pháp sắp xếp và tìm kiếm ngoài

Đầu tiên chia đôi số khoá trong F, một nửa sao lên F 1 và nửa còn lại sao
lên F2:
F1: A

S O R

F2: R


X N

S

F

T

I
T

Trộn khối một khoá đầu tiên của F1 với khối một khoá đầu tiên của F2 để
tạo ra hai khoá có thứ tự rồi ghi vào F:
F1: A

S O R

F2: R

T

I N

T

I

N G



F:AR
Tiếp theo ta trộn khối một khoá thứ hai của F 1 với khối một khoá thứ hai
của F2 để tạo ra hai khoá có thứ tự rồi ghi vào F:
F1: A

S O R

F2: R

T

I N

T

I

N G

A

N

D

M E

R G


FG

F2: A N N R D E M X E N R S G T I T
Tiếp tục trộn các khối tơng ứng trong F1 và F2 để tạo ra các khối bốn khoá
và ghi vào F, sau lần trộn này ta đợc:
F: A A N R N R S T D E I O M N R X A E N T I N R S G G N T
FGIT

14


Luận văn tốt nghiệp

Một số ph ơng pháp sắp xếp và tìm kiếm ngoài

Đến đây băng F chứa một dãy các khối bốn khoá. Lại tiếp tục chia nó
thành F1 và F2 bằng cách sao một nửa số khối lên F1 và nửa còn lại lên F2:
F1: A A N R

NRST

DEIO MNRX

F2: A E N T I N R S G G N T

FGIT

Trộn các khối tơng ứng trong F1 và F2 để tạo ra các khối tám khoá và ghi
vào F, sau lần trộn này ta đợc:
F: A A A E N N R T I N N R R S S T D E G G I N O T F G I M N R T X

15


Luận văn tốt nghiệp

Một số ph ơng pháp sắp xếp và tìm kiếm ngoài

bớc (nh ở 2 ví dụ trên: Trong ví dụ 2.1 số khoá là 25 (=25) bé hơn số khoá trong
ví dụ 2.2, song số bớc thực hiện sắp xếp vẫn phải là 5. Tức là bằng số bớc sắp xếp
trong ví dụ 2.2 ). Nh vậy phơng pháp sắp xếp này sẽ hiệu quả cao hơn đối với số
khoá cần sắp xếp là một luỹ thừa của 2 và khi này phơng pháp trộn trên sẽ đợc
gọi là phơng pháp sắp xếp kiểu trộn nhị phân. Vì vậy, chúng ta nên sử dụng phơng pháp này cho việc sắp xếp tập tin có số khoá là một luỹ thừa của 2.

2.2. Phơng pháp trộn tự nhiên
Phơng pháp trộn trực tiếp không tận dụng đợc việc từng đoạn của dữ liệu
ban đầu đã đợc sắp. Độ dài các khối đợc trộn ở bớc thứ k nhỏ hơn hay bằng 2k,
độc lập với việc có những khối dài hơn đã đợc sắp hay có thể đã đợc trộn. Thực
ra có thể trộn 2 khối bất kỳ đã đợc sắp với chiều dài m, n thành khối dài m+n.
Trộn tự nhiên là phơng pháp luôn luôn trộn 2 khối dài nhất có thể có. Phơng pháp
này đợc nêu ra nh sau:
Giả sử có 3 băng F, F 1, F2 dùng cho quá trình sắp xếp và ban đầu F gồm n
khoá, một số đoạn trong F chứa các phần tử đã đợc sắp thứ tự.
Bớc 1: Chia băng F một cách tự nhiên để đợc các khối có kích thớc khác
nhau, hay chứa số các khoá khác nhau (các khối này có thứ tự).
Sao các khối theo thứ tự luân phiên vào hai băng F 1 và F2. Sau đó trộn khối
đầu tiên của băng F1 với khối đầu tiên của băng F 2 để đợc một khối có thứ tự và
ghi vào F. Tiếp tục trộn các khối tơng ứng trong F1 và F2 để đợc các khối lớn hơn,
ghi vào F.
Bớc 2: Lại chia F bằng cách sao các khối theo thứ tự luân phiên vào hai
băng F1 và F2. Trộn các khối tơng ứng trong F1 và F2 để đợc các khối lớn hơn các

G

GIN

AMP

E

EX L

Trộn các khối tơng ứng trong F1 và F2 để tạo ra các khối có thứ tự trong F:
F: A O R S T

GIN

ADMN

EGINR EGX

ALMP E

Lại chia F thành F1 và F2 bằng cách sao các khối theo thứ tự luân phiên vào
2 băng F1 và F2:
F1: A O R S T
F2: G I N

ADMN

EGINR


Luận văn tốt nghiệp

Một số ph ơng pháp sắp xếp và tìm kiếm ngoài

F: A A D E G G I I M N N N O R R S T

AEEGLMPX

Trong bớc tiếp theo, chia F thành F 1 và F2 bằng cách sao các khối theo thứ
tự luân phiên vào 2 băng F1 và F2. Lúc này mỗi băng F1, F2 chỉ chứa một khối:
F1: A A D E G G I I M N N N O R R S T
F2: A E E G L M P X
Thực hiện trộn ở lần này, ta đợc:
F: 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
Nh vậy, nếu ta cũng xem mỗi lợt trộn và chia là 1 bớc thì quá trình sắp xếp
ở trên gồm có 4 bớc, giảm hơn một bớc so với sắp xếp trộn trực tiếp.

2.3. Trộn nhiều đờng cân bằng
Trộn nhiều đờng cân bằng là phơng pháp sắp xếp mà số băng từ để chứa
các khối đa vào trộn và số băng từ để chứa các khối đa ra sau khi trộn là bằng
nhau.
Băng từ để chứa các khối đa vào trộn gọi là băng Input và băng từ để chứa
các khối đa ra sau khi trộn gọi là băng output. Nh vậy số lợng băng input sẽ bằng
số lợng băng output. Nghĩa là nếu có n băng từ (với n chẵn) thì [n/2] băng từ đợc
làm băng input và [n/2] băng từ đợc làm băng output. Các khối trên [n/2] băng
input sẽ lần lợt đợc trộn theo thứ tự và đợc ghi luân phiên lên [n/2] băng output.
Sau mỗi lợt, khi các khối trên băng input đã hết thì vai trò của băng input và băng
output lại đổi cho nhau. Quá trình này cứ tiếp tục cho tới khi chỉ còn một khối
duy nhất trên một băng. Nh vậy ở đây áp dụng phơng pháp trộn n đờng. Để hiểu
một cách tờng minh về phơng pháp này, chúng ta xét ví dụ sau:

DMN

EGR

GIN

AEX

LMP E

Chúng ta thực hiện trộn 3 khối nên sử dụng 3 băng input và 3 băng output.
Đầu tiên sao luân phiên các khối lên 3 băng input và kết quả của bớc thứ nhất nh
sau:
F1: A O S D M N
F2: I R T
F3: A G N

AEX

EGR LMP
GNI

E

F4:
F5:
F6:
Tiếp theo ta sẽ thực hiện bớc 2:
Trộn các khối đầu tiên tơng ứng của băng F1, băng F2 và băng F3. Ta đợc
khối chín khoá (các khoá có thứ tự ) nh sau: A A G I N O R S T. Xuất khối này

Trên đây chỉ là một ví dụ cụ thể với số khoá rất nhỏ để minh hoạ cho phơng pháp trộn nhiều đờng cân bằng. Nhng tốt nhất là sử dụng tập tin lớn khi dùng
phơng pháp này.

2.4. Trộn nhiều giai đoạn

20


Luận văn tốt nghiệp

Một số ph ơng pháp sắp xếp và tìm kiếm ngoài

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 F 1, F2, F3 và ban đầu các khối đợc sắp

AIMNP AEGLN

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 F 2 và lúc này
băng F1 rỗng:
F1:
F2: A D E E G M O R R S T X

AGIIMNNP

F3: A E G L N
Một lần nữa trộn khối đầu tiên của băng F 2 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 F 1, 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

22

F3

13

8

3

5

0

8

2

1

0

5

3

1

1

0


Hình 2.1

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

16

15

14

12

8

23

4

2

1

0

2

2

2

1

0

1

1

1

1

0

1



0

1

1

1

1

2

2

2

1

3

3

3

2

5

24

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


4

4

3

2

17

4

8

8

7

6

4

33

5

16

15