Sắp xếp trong Pascal (tiếp theo)
- Thứ năm - 06/08/2020 09:35
- In ra
- Đóng cửa sổ này
Nội dung của phương pháp này là chia dãy cần sắp thành các dãy con đã có thứ tự (gọi là các Run) và có số phần tử là lũy thừa của 2, sau đó tìm cách trộn dần chúng với nhau thành các Run có thứ tự có chiều dài tăng dần cho đến khi chỉ còn một Run thì quá trình sắp xếp kết thúc.
f) Phương pháp trộn (Merging sort)
* Giải thích:
Nội dung của phương pháp này là chia dãy cần sắp thành các dãy con đã có thứ tự (gọi là các Run) và có số phần tử là lũy thừa của 2, sau đó tìm cách trộn dần chúng với nhau thành các Run có thứ tự có chiều dài tăng dần cho đến khi chỉ còn một Run thì quá trình sắp xếp kết thúc.
Ta có giải thuật sau đây để trộn 2 Run X và y cùng thứ tự có chiều dài lần lượt là m và n thành một Run z có chiều dài là m + n.
Procedure Merge;
Var
i, j, k: integer;
Begin
i:= 1;
j:= 1;
k:= 1;
while (i <= m) and (j <= n) do
Begin
If x[i] < y[j] then
Begin
z[k]:= x[i];
i := i + 1;
end;
Else
Begin
z[k]:= y[j];
j := j + 1;
end;
k:= k + 1;
end;
while i <= m do
Begin
z[k] := x[j];
k := k + 1;
i := k + 1;
i := i + 1;
end;
while j <= n do
Begin
z[k]:= y[j];
k := k + 1;
j := j + 1;
end;
End;
Cụ thể là nếu ta phải sắp xếp dãy: a[l], a[2], a[n].
Ta sử dụng 2*n phần tử được chia thành hai vùng. Vùng 1 gồm các phần tử a[l]..a[n], vùng 2 gồm các phần tử a[n+1]..a[2*n|. Ta trộn các Run từ vùng này và phân phối vào vùng kia. Khi trộn và phân phối, ta trộn các Run ngược chiều nhau của vùng trộn và phân phối luân phiên vào 2 đầu của vùng phân phối bước kế tiếp dễ trộn hơn. Quá trình sắp xếp sẽ kết thúc nếu vùng phân phối chỉ còn một Run. Khi kết thúc, nếu vùng phân phối gồm các phần tử a[n+l]..a[2*n] thì ta chép dãy a[n+1]..a[2*n] vào dãy a[l]..a[n].
* Ví dụ:
Sắp xếp dãy số:
39 50 7 37 89 13 1 62
• Bước 1: Vùng 1 là vùng trộn, vùng 2 là vùng phân phối:
Vùng 1: 39 50 7 37 89 13 1 62
-> -> -> -> <- <- <- <-
Vùng 2: 39 62 7 13 89 37 50 1
———> ———> <——— <———
• Bước 2: Vùng 2 là vùng trộn, vùng 1 là vùng phân phối:
Vùng 2: 39 62 7 13 89 37 50 1
———> ———> <——— <———
Vùng 1: 1 39 50 62 89 37 13 7
————————> <————————
Bước 3: Vùng 1 là vùng trộn, vùng 2 là vùng phân phối:
Vùng 1: 1 39 50 62 89 37 13 7
——————————————————>
Vùng 2: 1 7 13 37 39 50 62 89
• Bước 4: Chép các phần tử của vùng 2 vào vùng 1:
Vùng 2: 1 7 13 37 39 50 62 89
Vùng 1: 1 7 13 37 39 50 62 89
* Thể hiện bằng PASCAL:
CHÚ Ý:
• Ta khai báo:
Var a: array[1..2* n] of item ;
Đặt up: Bollean
up = True: vùng 1 là vùng trộn, vùng 2 là vùng phân phối.
up = false: vùng 2 là vùng trộn, vùng 1 là vùng phân phối.
d: cho biết chiều phân phôi
d = 1: chiều phân phôi tăng dần.
d = -1: chiều phân phối giảm dần.
p = chiều dài của run khi trộn.
m = số phần tử chưa được trộn và phân phối.
s, t = chiều dài của hai run đang trộn.
• Cụ thể là:
Procedure Merge_Sort;
Var
up: Bollean;
i, j, k, q, t, r, s, d, p: integer;
Begin
up := true;
p := 1
repeat
d := 1;
m := n;
if up then
Begin
i := 1; j := n;
k := n + 1; q := 2* n
end
else
Begin
i:= n + 1; j:= 2 * n;
k:= 1; q:= n
end;
Repeat
if m >= p then s := p else s := m; m:= m - s
' while (s < > 0) and (r < > 0) do
Begin
if a[i].key < a[j].key then
Begin
a[k] := a[i];
i := i + 1; s := s - 1;
end;
else
Begin
a[k]:= a[j];
j := j - 1;
r := r - 1;
end;
k:= k + d;
end;
while s < > do
Begin
a[k]:= a[i];
k := k + d;
i := i + 1;
s := s - 1;
end;
while r < > 0 do
Begin
a[k]:= a[j];
k:= k + d;
j := j - 1;
r := r - 1;
end;
d := -d;
t := k; k := q; q := 1;
until m = 0;
up := not up;
p := 2*p
until p >= n;
if not up then
For i := 1 to n do a[i]:= a[i + n]
end;
3. SẮP XẾP NGOÀI (SẮP XẾP TẬP TIN)
a) Khái niệm
Tất cả các phương pháp sắp xếp trong đã trình bày ở trên đều đòi hỏi phải đưa toàn bộ dữ liệu cần sắp vào bộ nhớ chính nên không thể dùng để sắp thứ tự các tập tin có chiều dài tương đối lớn vì không thể nạp toàn bộ tập tin vào bộ nhớ chính để sắp xếp, do đó ta phải có phương pháp khác thích hợp cho việc sắp xếp các tập tin.
Phương pháp căn bản để sắp xếp một tập tin là:
- Phân chia tập tin nguồn thành các tập tin nhỏ hơn,
- Nạp vào các tập tin đó vào bộ nhớ chính.
- Dùng các phương pháp sắp xếp trong để sắp xếp chúng thành các run.
- Trộn các run này lại và đưa vào tập tin đích.
Trong đó hai bước quan trọng nhất là:
- Tạo các run ban đầu.
- Trộn các run với nhau.
Để đơn giản hóa vấn đề ở đây ta chỉ xét các phương pháp trộn run kích thước cố định của dãy.
b) Ví dụ
Ta xét 3 tập tin f[0], i[1], f[2] với f[0] là tập tin cần sắp xếp. Ta sẽ phân phối các run của f[0]ư và f[l], f[2] và trộn các run này vào tập tin f[0]. Nếu sau khi trộn mà f[0] chỉ có một run thì kết thúc thuật giải. Ngược lại nếu f[0] có nhiều hơn một run thì ta lặp lại bước phân phôi và trộn các run.
Ban đầu, f[0] chứa các khóa:
17 31 05 59 13 41 43 67 11 23 29 47 03 07 71 02 19 57 37 61
• Bước 1: Phân phối các run có chiều dài bằng 1 của f[0] vào f[1] và f[2]
f[1] 17 05 13 43 11 29 03 71 19 37
f[2] 31 59 41 67 23 47 07 02 57 61
• Bước 2: Trộn các run của f[1] và f[2] vào f[0]
F[0] 17 31 05 59 13 41 43 67 11 23 29 47
03 07 02 71 19 57 37 61
• Bước 3 : Phân phối các run cỏ chiều dài bằng 2 của f[0] vào f[l] và f[2]
f[1] 13 31 14 41 11 23 03 07 19 57
f[2] 05 59 43 67 29 47 02 71 37 61
• Bước 4 : Trộn các run của f[l] và f[2] vào f[0]
f[0] 05 17 31 59 13 41 43 67 11 23 29 47
02 03 07 71 19 37 57 61
• Bước 5 : Phân phối các run có chiều dài bằng 4 của f[0] vào f[l] và f[2]
f[l] 05 17 31 59 11 23 29 47 19 37 57 61
f[2] 13 41 43 67 02 03 07 71
• Bước 6: Trộn các run của f[1] và f[2] vào f[0]
f[0] 05 13 17 31 41 43 59 67 02 03 07 11
23 29 47 71 19 37 57 61
• Bước 7: Phân phối các run có chiều dài bằng 8 của f[0] vào f[1] và f[2]
f[1] 05 13 17 31 41 43 59 67 19 37 57 61
f[2] 02 03 07 11 23 29 47 71
• Bước 8: Trộn các run của f[l] và f[2] vào f[0]
f[0] 02 03 05 07 11 13 17 23 29 31 41 43 47 59 67 71
19 37 57 61
• Bước 9: Phân phối các run có chiều dài bằng 16 của f[0] vào f[1] và f[2]
f[1] 02 03 05 07 11 13 17 23 29 31 41 43 47 59 67 71
f[2] 19 37 57 61
• Bước 10: Trộn các run của f[1] và f[2] vào f[0]
f[0] 02 03 05 07 11 13 17 19 23 29 31 37 41 43 47 57
59 61 67 71
Ta khai báo:
Type
tape = file of item;
Var
f: array[0..2] of tape;
Gọi: n - số mẫu tin của tập tin f[0]
Thủ tục Distribute phân phối các run có chiều dài bằng p của f[0] luân phiên vào f[1] và f[2J.
c) Thể hiện bằng PASCAL:
Procedure Merge_Sort;
Var
p, q, r, m: integer;
x1, x2: item;
Procedure Distribute (p: integer);
{Phân phôi các run có chiều dài bằng p của f[0] vào f[1] và f[2]}
Var
k, i: integer;
buf: item;
begin
reset (f[0]); rewrite (f[1]); rewrite (f[2]);
k := 1;
i := 0; .
while not eof (f[0]) do
begin
i := i + 1;
read (f[0], buf);
write (f[k], buf);
if i = p then
begin
i := 0;
if k = 1 then k:= 2 else k:= 1
end;
end;
rewrite (f[0]); reset (f[1]); reset (f[2]);
end; {Distribute}
BEGIN (Merge.Sortl
p:= 1;
repeat
{phân phối các run có chiều dài bằng p của f[0] vào f[1] và f[2]) ;
Distribute(p)
m:= n;
read (f[1], x1) ; {run q}
read (f[2], x2) ; {run r}
repeat
if m >= p then q := p else q := m;
m := m - q;
if m >= p then r := p else r := m;
m := m - r;
while (p < > 0) and (r < > 0) do {chưa hết run q và run r}
if x1.key < x2.key then
begin
write (f[0], x1);
q := q - 1;
if not eof (f[1]) then read (f[1], x1) ;
end;
else
begin
write (f[0], x2);
r := r - 1;
if not eof (f[2]) then read x2):
end;
while q < > 0 do {chưa hết run q}
begin
write (f[0], x1);
q := q - 1;
if not eof (f[1]) then read (f[1], x1);
end;
while r < > 0 do {chưa hết run r}
begin
write (f[0], x2);
r := r - 1;
if not eof (f[2] then read (f[2], x2) ,
end;
until m = 0;
p := 2*p ; {tăng chiều dài của run}
until p >= n;
END;
* Giải thích:
Nội dung của phương pháp này là chia dãy cần sắp thành các dãy con đã có thứ tự (gọi là các Run) và có số phần tử là lũy thừa của 2, sau đó tìm cách trộn dần chúng với nhau thành các Run có thứ tự có chiều dài tăng dần cho đến khi chỉ còn một Run thì quá trình sắp xếp kết thúc.
Ta có giải thuật sau đây để trộn 2 Run X và y cùng thứ tự có chiều dài lần lượt là m và n thành một Run z có chiều dài là m + n.
Procedure Merge;
Var
i, j, k: integer;
Begin
i:= 1;
j:= 1;
k:= 1;
while (i <= m) and (j <= n) do
Begin
If x[i] < y[j] then
Begin
z[k]:= x[i];
i := i + 1;
end;
Else
Begin
z[k]:= y[j];
j := j + 1;
end;
k:= k + 1;
end;
while i <= m do
Begin
z[k] := x[j];
k := k + 1;
i := k + 1;
i := i + 1;
end;
while j <= n do
Begin
z[k]:= y[j];
k := k + 1;
j := j + 1;
end;
End;
Cụ thể là nếu ta phải sắp xếp dãy: a[l], a[2], a[n].
Ta sử dụng 2*n phần tử được chia thành hai vùng. Vùng 1 gồm các phần tử a[l]..a[n], vùng 2 gồm các phần tử a[n+1]..a[2*n|. Ta trộn các Run từ vùng này và phân phối vào vùng kia. Khi trộn và phân phối, ta trộn các Run ngược chiều nhau của vùng trộn và phân phối luân phiên vào 2 đầu của vùng phân phối bước kế tiếp dễ trộn hơn. Quá trình sắp xếp sẽ kết thúc nếu vùng phân phối chỉ còn một Run. Khi kết thúc, nếu vùng phân phối gồm các phần tử a[n+l]..a[2*n] thì ta chép dãy a[n+1]..a[2*n] vào dãy a[l]..a[n].
* Ví dụ:
Sắp xếp dãy số:
39 50 7 37 89 13 1 62
• Bước 1: Vùng 1 là vùng trộn, vùng 2 là vùng phân phối:
Vùng 1: 39 50 7 37 89 13 1 62
-> -> -> -> <- <- <- <-
Vùng 2: 39 62 7 13 89 37 50 1
———> ———> <——— <———
• Bước 2: Vùng 2 là vùng trộn, vùng 1 là vùng phân phối:
Vùng 2: 39 62 7 13 89 37 50 1
———> ———> <——— <———
Vùng 1: 1 39 50 62 89 37 13 7
————————> <————————
Bước 3: Vùng 1 là vùng trộn, vùng 2 là vùng phân phối:
Vùng 1: 1 39 50 62 89 37 13 7
——————————————————>
Vùng 2: 1 7 13 37 39 50 62 89
• Bước 4: Chép các phần tử của vùng 2 vào vùng 1:
Vùng 2: 1 7 13 37 39 50 62 89
Vùng 1: 1 7 13 37 39 50 62 89
* Thể hiện bằng PASCAL:
CHÚ Ý:
• Ta khai báo:
Var a: array[1..2* n] of item ;
Đặt up: Bollean
up = True: vùng 1 là vùng trộn, vùng 2 là vùng phân phối.
up = false: vùng 2 là vùng trộn, vùng 1 là vùng phân phối.
d: cho biết chiều phân phôi
d = 1: chiều phân phôi tăng dần.
d = -1: chiều phân phối giảm dần.
p = chiều dài của run khi trộn.
m = số phần tử chưa được trộn và phân phối.
s, t = chiều dài của hai run đang trộn.
| Vùng trộn | |
| Vùng phân phối |
Procedure Merge_Sort;
Var
up: Bollean;
i, j, k, q, t, r, s, d, p: integer;
Begin
up := true;
p := 1
repeat
d := 1;
m := n;
if up then
Begin
i := 1; j := n;
k := n + 1; q := 2* n
end
else
Begin
i:= n + 1; j:= 2 * n;
k:= 1; q:= n
end;
Repeat
if m >= p then s := p else s := m; m:= m - s
' while (s < > 0) and (r < > 0) do
Begin
if a[i].key < a[j].key then
Begin
a[k] := a[i];
i := i + 1; s := s - 1;
end;
else
Begin
a[k]:= a[j];
j := j - 1;
r := r - 1;
end;
k:= k + d;
end;
while s < > do
Begin
a[k]:= a[i];
k := k + d;
i := i + 1;
s := s - 1;
end;
while r < > 0 do
Begin
a[k]:= a[j];
k:= k + d;
j := j - 1;
r := r - 1;
end;
d := -d;
t := k; k := q; q := 1;
until m = 0;
up := not up;
p := 2*p
until p >= n;
if not up then
For i := 1 to n do a[i]:= a[i + n]
end;
3. SẮP XẾP NGOÀI (SẮP XẾP TẬP TIN)
a) Khái niệm
Tất cả các phương pháp sắp xếp trong đã trình bày ở trên đều đòi hỏi phải đưa toàn bộ dữ liệu cần sắp vào bộ nhớ chính nên không thể dùng để sắp thứ tự các tập tin có chiều dài tương đối lớn vì không thể nạp toàn bộ tập tin vào bộ nhớ chính để sắp xếp, do đó ta phải có phương pháp khác thích hợp cho việc sắp xếp các tập tin.
Phương pháp căn bản để sắp xếp một tập tin là:
- Phân chia tập tin nguồn thành các tập tin nhỏ hơn,
- Nạp vào các tập tin đó vào bộ nhớ chính.
- Dùng các phương pháp sắp xếp trong để sắp xếp chúng thành các run.
- Trộn các run này lại và đưa vào tập tin đích.
Trong đó hai bước quan trọng nhất là:
- Tạo các run ban đầu.
- Trộn các run với nhau.
Để đơn giản hóa vấn đề ở đây ta chỉ xét các phương pháp trộn run kích thước cố định của dãy.
b) Ví dụ
Ta xét 3 tập tin f[0], i[1], f[2] với f[0] là tập tin cần sắp xếp. Ta sẽ phân phối các run của f[0]ư và f[l], f[2] và trộn các run này vào tập tin f[0]. Nếu sau khi trộn mà f[0] chỉ có một run thì kết thúc thuật giải. Ngược lại nếu f[0] có nhiều hơn một run thì ta lặp lại bước phân phôi và trộn các run.
Ban đầu, f[0] chứa các khóa:
17 31 05 59 13 41 43 67 11 23 29 47 03 07 71 02 19 57 37 61
• Bước 1: Phân phối các run có chiều dài bằng 1 của f[0] vào f[1] và f[2]
f[1] 17 05 13 43 11 29 03 71 19 37
f[2] 31 59 41 67 23 47 07 02 57 61
• Bước 2: Trộn các run của f[1] và f[2] vào f[0]
F[0] 17 31 05 59 13 41 43 67 11 23 29 47
03 07 02 71 19 57 37 61
• Bước 3 : Phân phối các run cỏ chiều dài bằng 2 của f[0] vào f[l] và f[2]
f[1] 13 31 14 41 11 23 03 07 19 57
f[2] 05 59 43 67 29 47 02 71 37 61
• Bước 4 : Trộn các run của f[l] và f[2] vào f[0]
f[0] 05 17 31 59 13 41 43 67 11 23 29 47
02 03 07 71 19 37 57 61
• Bước 5 : Phân phối các run có chiều dài bằng 4 của f[0] vào f[l] và f[2]
f[l] 05 17 31 59 11 23 29 47 19 37 57 61
f[2] 13 41 43 67 02 03 07 71
• Bước 6: Trộn các run của f[1] và f[2] vào f[0]
f[0] 05 13 17 31 41 43 59 67 02 03 07 11
23 29 47 71 19 37 57 61
• Bước 7: Phân phối các run có chiều dài bằng 8 của f[0] vào f[1] và f[2]
f[1] 05 13 17 31 41 43 59 67 19 37 57 61
f[2] 02 03 07 11 23 29 47 71
• Bước 8: Trộn các run của f[l] và f[2] vào f[0]
f[0] 02 03 05 07 11 13 17 23 29 31 41 43 47 59 67 71
19 37 57 61
• Bước 9: Phân phối các run có chiều dài bằng 16 của f[0] vào f[1] và f[2]
f[1] 02 03 05 07 11 13 17 23 29 31 41 43 47 59 67 71
f[2] 19 37 57 61
• Bước 10: Trộn các run của f[1] và f[2] vào f[0]
f[0] 02 03 05 07 11 13 17 19 23 29 31 37 41 43 47 57
59 61 67 71
Ta khai báo:
Type
tape = file of item;
Var
f: array[0..2] of tape;
Gọi: n - số mẫu tin của tập tin f[0]
Thủ tục Distribute phân phối các run có chiều dài bằng p của f[0] luân phiên vào f[1] và f[2J.
c) Thể hiện bằng PASCAL:
Procedure Merge_Sort;
Var
p, q, r, m: integer;
x1, x2: item;
Procedure Distribute (p: integer);
{Phân phôi các run có chiều dài bằng p của f[0] vào f[1] và f[2]}
Var
k, i: integer;
buf: item;
begin
reset (f[0]); rewrite (f[1]); rewrite (f[2]);
k := 1;
i := 0; .
while not eof (f[0]) do
begin
i := i + 1;
read (f[0], buf);
write (f[k], buf);
if i = p then
begin
i := 0;
if k = 1 then k:= 2 else k:= 1
end;
end;
rewrite (f[0]); reset (f[1]); reset (f[2]);
end; {Distribute}
BEGIN (Merge.Sortl
p:= 1;
repeat
{phân phối các run có chiều dài bằng p của f[0] vào f[1] và f[2]) ;
Distribute(p)
m:= n;
read (f[1], x1) ; {run q}
read (f[2], x2) ; {run r}
repeat
if m >= p then q := p else q := m;
m := m - q;
if m >= p then r := p else r := m;
m := m - r;
while (p < > 0) and (r < > 0) do {chưa hết run q và run r}
if x1.key < x2.key then
begin
write (f[0], x1);
q := q - 1;
if not eof (f[1]) then read (f[1], x1) ;
end;
else
begin
write (f[0], x2);
r := r - 1;
if not eof (f[2]) then read x2):
end;
while q < > 0 do {chưa hết run q}
begin
write (f[0], x1);
q := q - 1;
if not eof (f[1]) then read (f[1], x1);
end;
while r < > 0 do {chưa hết run r}
begin
write (f[0], x2);
r := r - 1;
if not eof (f[2] then read (f[2], x2) ,
end;
until m = 0;
p := 2*p ; {tăng chiều dài của run}
until p >= n;
END;
Bản quyền bài viết thuộc về Sachgiai.com. Ghi nguồn Sách giải.com khi đăng lại bài viết này.