Chương 7 sắp sếp SORTING
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (305.44 KB, 114 trang )
254
Chương 7
Sắp sếp - SORTING
Vấn đề sắp xếp có vai trò quan trọng
trong các bài toán thực tế. Chẳng hạn để xử lý
một tệp hoá đơn thanh toán trong một ngân
hàng người ta sắp xếp tệp hoá đơn đó theo thứ
tự tăng dần của số hiệu hoá đơn. Trong một
biểu tổng hợp kết quả kinh doanh cần sắp xếp
cột tiền bán hàng theo chiều tăng dần hay giảm
dần. Việc sắp xếp theo một trường nào đó (gọi
là trường khoá) tạo điều kiện thuận lợi cho
việc tìm kiếm thông tin. Yêu cầu tìm kiếm
cũng xuất hiện thường xuyên trong các bài
toán thực tế, chẳng hạn tìm kiếm một hoá đơn
khi cho số hiệu của hoá đơn ấy.v.v..
Một giải thuật sắp thứ tự được gọi là tốt
nếu giải thuật này đòi hỏi vùng nhớ nhỏ và
thời gian thực hiện nhanh. Tuy nhiên, việc
đánh giá giải thuật còn phụ thuộc vào thứ tự
xuất hiện của các phần tử trong dãy ban đầu;
254
255
dãy ban đầu đã có thứ tự hay chưa có thứ tự
theo vùng khoá.
Để tốn ít vùng nhớ thì giải thuật phải sử
dụng hữu hiệu các vùng nhớ của các phần tử
và hạn chế việc sử dụng các vùng nhở tạm
thời.
Để đánh giá thời gian thực hiện của giải
pháp sắp thứ tự, ta phải dựa vào hai đại lượng
đặc trưng là số lần so sánh (C) và số lần đổi
chỗ hai phần tử (M). Hai đại lượng C và M
phụ thuộc vào tính chất thống kê của dãy các
phần tử và phụ thuộc vào số phần tử cần sắp
thứ tự (n).
Các giải thuật sắp thứ tự có thể được chia
thành ba nhóm chính:
- Sắp thứ tự bằng phương pháp xen vào
( Insertion)
- Sắp thứ tự bằng phương pháp chọn lựa
(Selection)
- Sắp thứ tự bằng phương pháp đổi chỗ
( Exchange)
255
256
Trong chương này, chúng ta sẽ đề cập đến một
số giải thuật sắp xếp cơ bản .
7.1 Một số khái niệm về sắp xếp theo khoá
Giả sử ta xét vấn đề xử lý một tệp hoá
đơn trong ngân hàng, mỗi hoá đơn gồm các
trường sau đây:
Số hiệu hoá đơn
Tên người gửi tiền
Số lượng tiền gửi
Ngày gửi
Như vậy vấn đề sắp xếp tệp hoá đơn
theo trường khoá số hiệu hoá đơn có thể phát
biểu tổng quát là bài toán sắp xếp với một
bảng gồm n bản ghi R1, R2, ... Rn.
Mỗi hoá đơn có cấu trúc như sau:
SHHD
tên
Họ Tiền gửi Ngày gửi
256
257
Key
Trong quá trình sắp xếp các bản ghi
của tệp hoá đơn sẽ được bổ trí lại các vị trí sao
cho giá trị khoá trong trường tương ứng với
chúng có đúng thứ tự ấn định. Ta thấy kích
thước của khoá thường là khá nhỏ so với kích
thước của bản ghi (Chẳng hạn trong trường
hợp trên đây khoá là số hiệu hoá đơn chỉ
chiếm 1/5 của bản ghi). Nếu việc sắp xếp được
thực hiện trên tất cả các bản ghi của tệp sẽ dẫn
đến việc chuyển đổi vị trí của tất cả các bản
ghi, tức là phải sao chép toàn bộ bản ghi vào
các vùng nhớ mới, làm tốn rất nhiều không
gian nhớ. Để khắc phục điều này người ta xây
dựng một bảng phụ cũng gồm n bản ghi như
bảng chính nhưng mỗi bản ghi của nó chỉ bao
gồm hai trường là khoá và con trỏ. Trường
khoá chứa giá trị của khoá ứng với từng bản
ghi trong bảng chính, trường con trỏ, trỏ tới
bản ghi tương ứng. Bảng phụ này gọi là bảng
khoá ( Key table) và việc sắp xếp sẽ được thực
hiện trực tiếp trên bảng khoá đó. Như vậy
257
258
trong quá trình sắp xếp bảng chính không hề
bị ảnh hưởng gì, còn việc truy nhập vào bản
ghi nào đó của bảng chính vẫn có thể thực hiện
được bằng cách dựa vào con trỏ của bản ghi
tương ứng thuộc bảng khoá này.Sơ đồ sau đây
cho thấy mối liên hệ giữa bảng khoá và bảng
chính:
Bảng khoá
75
*
Bảng chính
75 Tên Số
lượng
42
*
42
Tên Số
lượng
38
*
38
Tên Số
lượng
80
*
80
Tên Số
lượng
Key
Ke
y
258
259
Sau khi sắp xếp theo chiều tăng dần của trường
khoá ta có:
38
*
75
Tê
n
Số lượng
42
*
42
Tê
n
Số lượng
75
*
38
Tê
n
Số lượng
80
*
80
Tê
n
Số lượng
Key
Ke
y
Như vậy, rõ ràng là khoá có vai trò
đặc biệt quan trọng so với các trường khác, nó
là đại diện cho các bản ghi. Do đó khi trình
bày giải thuật với các bản ghi chúng ta chỉ nói
tới giá trị khoá. Bài toán sắp xếp đối với các
259
260
bản ghi R1, R2......Rn thực chất là bài toán sắp
xếp với dãy khoá K1,,K2....Kn.
Trong các thuật toán dưới đây, chúng ta
giả sử trường khoá chứa các giá trị số và trình
tự sắp xếp là tăng dần [1,2].
7.2 sắp xếp kiểu lựa chọn (Selection Sort)
Tư tưởng chủ đạo của giải thuật sắp xếp
kiểu lựa chọn là ở lượt thứ I ta sẽ chọn trong
dãy khoá Ki, Ki+1,....Kn khoá nhỏ nhất và đổi
chỗ với Kj.
Như vậy sau J lượt, J khoá nhỏ hơn đã
lần lượt ở các vị trí thứ nhất, thứ hai... thứ J
theo đúng thứ tự sắp xếp[1].
Chúng ta minh hoạ giải thuật bằng ví dụ
sau đây:
Giả sử số hiệu của các hoá đơn được đánh số
là:
42 23
58 94
74
36
11 55
99 87
260
261
ở bước thứ nhất ta thấy 11 là số hiệu
hoá đơn nhỏ nhất, ta đổi chỗ lần lượt cho 74,
23 và 42. Bây giờ số hiệu hoá đơn 11 đứng ở
đầu dãy khoá. Trong các khoá còn lại, số hiệu
hoá đơn 23 là nhỏ nhất. ở bước 3 trong các
khoá còn lại (42,74,55,58,94,36,99,87) khoá
nhỏ nhất là 36. Và trình tự này tiếp diễn cho
đến kết thúc dãy khoá.
Giải thuật như sau:
Procedure Select _ Sort(k: Vector;
var n : integer);
Var
x: real;
i,j , m: integer;
Begin
For I : = 1 to n-1 do
Begin
m : =I;
For J : = i+1 to n
do
261
262
= j;
If k[j]
end;
end;
Begin
x : = ki;
ki : = km;
km : = x;
end;
Trong giải thuật này ở lệnh k đầu tiên
biến I nhận giá trị từ 1 đến n -1 (chứ không
phải là đến n) vì phép so sánh ở dưới J : = I+1,
điều này đảm bảo cho việc so sánh được thực
hiện với đúng n khoá.
7. 3
Giải thuật sắp xếp kiểu thêm dần
( Insertion Sort)
ý tưởng của phương pháp này như sau:
ở giai đoạn đầu ta coi như chỉ có một thành
262
263
phần K1(một phần tử). Sau đó xét thêm K 2, so
sánh với K1 để xác định vị trí “chèn” của nó
( về phía trái hay phía phải của K1). Bây giờ ta
xét thêm K3 và so sánh nó với bảng gồm 2
khoá K1 và K2 đã được sắp xếp để xác định vị
trí “ chèn” K3 vào trong bảng. Kết quả là ta
được bảng 3 khoá K1, K2, K3 đã được sắp xếp
và quá trình cứ thế tiếp diẽn như vậy cho đến
hết dãy khoá [1,2].
Giải thuật như sau:
Procedure InsertionSort ( k : Vector; Var
n : integer);
Var
x: real;
i, j:integer;
Begin
ko : = -99999999.9;
( *coi như K0 = - *)
For I : = 2 to n do
Begin
x : = kI;
263
264
J : = I-1;
While x< kJ
do
Begin
kJ +1 : =
kJ;
end;
J : = J-1;
end;
kJ +1 : = x;
end ;
Trong giải thuật này ta dùng x làm ô
nhớ phụ chứa khoá mới đang xét. Khoá mới
đều được chèn vào giữa khoá nhỏ hơn nó và
khoá lớn hơn nó. Ta đưa thêm vào khoá K 0 có
giá trị nhỏ hơn mọi khoá của bảng và đứng
trước mọi khoá khác .
7.4 Giải thuật sắp xếp kiểu đổi chỗ
( Exchange Sort)
264
265
Tư tưởng của giải thuật như sau: Toàn bộ
các khoá được duyệt từ đáy lên đỉnh. Nếu gặp
hai khoá kế cận ngược thứ tự thì đổi chỗ chúng
cho nhau. Như vậy lần đầu khoá có giá trị nhỏ
nhất sẽ chuyển dần lên đỉnh và ở vị trí đầu
tiên. Lần thứ hai khoá có giá trị nhỏ thứ hai sẽ
chuyển dần lên chiếm vị trí thứ hai v.v...Như
vậy các khoá có giá trị nhỏ sẽ “ nổi” dần lên
trên, các khoá có giá trị lớn sẽ “chìm” dần
xuống dưới vì vậy người ta còn gọi phương
pháp này là giải thuật sắp xếp kiểu “bọt nước”
[1,2]
Giải thuật được viết dưới dạng một thủ tục như
sau:
Procedure Bubble _ Sort(k : Vector; Var n :
integer);
Var
i,j: integer;
x: real;
Begin
For I : = 1 to
n-1 do
For J : = n down to i+1 do
265
266
If kJ < kj
-1 then
Begin
x:=
kj;
kJ : =
kj -1;
kj -1 :
= x;
end;
end;
7.5 Sắp xếp nhanh (Quick Sort)
Từ việc phân tích giải thuật đổi chỗ ta
thấy một vấn đề sau đây:
Sau lượt thứ ba ngoài ba khoá 11, 23,
35 đã được sắp xếp còn 2 khoá nữa (42,58) đã
được sắp xếp và ở lượt thứ 4 toàn bộ khoá đã
được sắp xếp xong. Năm lượt sắp xếp cuối
không còn tác dụng gì nữa. Do đó có thể cải
266
267
tiến giải thuật này để giảm số lần tính toán.
A.R Harre đã cải tiến như sau:
Chọn một khoá ngẫu nhiên nào đó của
dãy làm “chốt” (Pivot). Mọi phần tử nhỏ hơn
chốt được “xếp vào vị trí sau chốt( Tức là phần
tử cuối dãy). Muốn vậy, các phần tử trong dãy
sẽ được so sánh với khoá chốt và sẽ đổi vị trí
cho nhau hoặc cho chốt hoặc nó lớn hơn chốt
mà lại nằm trước chốt hoặc nhỏ hơn chốt mà
lại nằm sau chốt. Khi đổi chỗ xong, dãy số đã
được phân chia thành hai đoạn: Một đoạn gồm
các khoá nhỏ hơn chốt, một đoạn gồm các
khoá lớn hơn chốt, còn khoá chốt thì nằm giữa
hai đoạn trên đây. ở các bước sau cũng áp
dụng kỹ thuật tương tự đối với các phân đoạn
còn lại.
Một đoạn được xử lý ngay còn một
đoạn được ghi nhớ lại. Quá trình xử lý như vậy
cứ tiếp tục cho tới khi gặp một phân đoạn chỉ
gồm có hai phần tử thì không cần ghi nhớ nữa.
Lúc đó một phân đoạn mới sẽ được xác định
mà đối với phân đoạn này quá trình lặp lại
267
268
tương tự. Sắp xếp kết thúc khi phân đoạn cuối
cùng đã được xử lý xong.
Giải thuật đệ qui như sau [2]:
Giả sử cho bảng khoá K gồm n bản
ghi. Trong giải thuật sử dụng một bản ghi giả
có khoá tương ứng là KJ +1 mà Ki < Kn
+1 với 1 < I < n.
Duoi và Tren là hai biến của bảng được xử lý.
Lúc đầu Duoi =1 còn Tren = n, hai chỉ số I và J
dùng để lựa chọn khoá trong quá trình xử lý,
Key là biến chứa giá trị của chốt. B là một biến
logic, khi B = false thì bảng được phân thành
hai bảng con.
Procedure QuickSort (k : Vector; Var :
duoi, tren : integer);
Var
i,j: integer;
key: real;
Begin
B : = True;
If duoi < tren then
Begin
268
269
I : = duoi;
J : = tren +1;
key : = kduoi;
While B do
Begin
i : = I+1 ;
if ki < key then begin i : =
i+1;
J : = J-1;
end;
if kj > key then J : = J-1;
If I< J then
begin
x : = k[i];
k[i] : = k[j];
k[j]: = x;
end
Else
B : = False;
End;
x : = k[duoi] ;
k[duoi] : = k[ j ];
269
270
k[j ]: = x;
QuickSort (k,duoi, J-1);
QuickSort(k,J+1, tren);
end;
end;
270
271
7.1 Phương pháp đếm
Nội dung của phương pháp này là đếm số phần
tử có khoá nhỏ hơn hay bằng khoá của phần tử
a(i). Nếu có j phần tử có khoá nhỏ hơn khoá
của phần tử a(i) sẽ có vị trí thứ (j + 1) trong
dây đã có thứ tự.
Trong giải thuật, ta dùng mảng count [i] (i =
1,2,..,n) với count[i] cho biết số phần tử có
khoá nhỏ hơn khoá của phần tử a[i]. Như vậy,
count [i] + 1 vị trí của phần tử a[i] trong dãy
đã có thứ tự.
Ví dụ: Ta cần sắp thứ tự dãy 44 55 12 42 94 18
06 67
i:
1
2
3
4
5
6
7
8
a
:
44 55 12 42 94 18 06 67
count
:
4
5
1
3
7
2
0
6
Như vậy, phần tử có khoá 55 ở vị trí thứ 6
(conut[2] = 5) và phần tử có khoá 18 ở vị trí
thứ 3 (count[6] = 2) trong dãy có thứ tự.
271
272
Giải thuật như sau :
272
273
Procedure Comparison - Counting;
Var
count: array [1..n] of integer;
s: array [1..n] of item
i,j: Integer
begin
for i : = 1 to n do count [i]: = 0 ;
for i : = n downto 2 do
for j: = i-1 downto 1 do
if a[i], key < a[j], key then count [j]: = count[j]
+1
else count [i]: = count [i] + 1
{di chuyển các phần tử a[i]}
for i : = 1 to n do s[count [i] + 1]: = a[i]
for i: = 1 to n do a[i]: = s[i]
end
Trường hợp nếu ta không dùng mảng s để di
chuyển các phần tử về đúng vị trí của nó trong
dãy có thứ tự thì ta có thể sử dụng các biến
tạm. Sau khi di chuyển phần tử a[i] đến vị trí
thứ count[i] + 1 thì ta cho count[i] bằng -1.
Quá trình di chuyển các phần tử của mảng a sẽ
273
274
kết thức khi tất cả các phần tử của mản count
bằng -1. Giải thuật được viết lại như sau:
Proceure Comparison - Counting;
var
Count: array [1.. n ] of Integer ;
y, t,i, j: integer ;
cont: boolcan ;
x, z: item;
begin
for i: = 1 to n do count [i] : = 0
for i: = n downto 2 do
for j: i - 1 dowmto 1 do
if a[ikey < a[j, key then count [j]: = count[j] +
1
else count [i]: = count [i + 1] ;
{di chuyển các phần tử a[i]}
i : = 1; cont: = truc;
while i < = n do
begin
if count[i <> - 1 then
begin
x: = a[i]; y: = count[i ] + 1;
274
275
count[i]: = 1;
Repeat
z: = a[y]; a[y]: = x;
t: = count[y]; count[y]: = 1;
x: = z; y: = t + 1;
Until y = 0
end ;
i: = i + 1 ;
end ;
end ;
Ghi chú:
Khoá cửa các phần tử của mảng a có thể trùng
nhau
Ví dụ: Sắp thứ tự dãy 3 1 5 2 7 6 5 4
i
:
1
2
3
4
5
6
7
8
a
:
3
1
5
2
7
6
5
4
count
:
2
0
4
1
7
6
5
3
Phân tích phương pháp đếm
275
276
Số lần so sánh : C = n* (n - 1)/2 . Số lần di
chuyển : sau khi được mảng count, ta chuyển
phần tử a[i] đến vị trí thứ count[i] + 1, do đó
số lần di chuyển là M = n
7.2 Phương pháp đếm và phân phối
Điều kiện để áp dụng phương pháp này là các
khoá cần sắp thứ tự phải ở trọng đoạn [u,v]
nhỏ và có giá trị nguyên.
Nội dung của phương pháp này là sắp thứ tự
các phần tử a[i] (i = 1,2,..,n) vào dãy có thứ tự
s[i] (i = 1,2,..,n). Mảng count có phần tử
count[j] (i = u; u + 1,..,v) đếm số phần tử của
mảng a có khoá là j.
Giải thuật như sau :
Procedure Distribution - Counting:
Var
s: array [1..n] of item;
count: array [u..v] of integer ;
i, j: integer ;
begin
276
277
for j : = u to v do count [j]: = 0 ;
for j: = 1 to n do count[a[j].key]: =
count[a[j].key] + 1 ;
for i: = u + 1 to v do count [i]: = count[i] +
count[i -1] ;
for j: = n downto 1 do
begin
i: = count[a[j] . key];
a[i] : = a[j];
count[a[j].key] : = i - 1 ;
end ;
end;
7.3 Sắp thứ tự bằng phương pháp xen vào
7.3.1 Phương pháp xen vào trực tiếp
Nội dung của phương này là giả sử ta có dây
a[1]- a[i-1] đã có thứ tự, ta phải xác định vị trí
thích hợp của phần tử a[i] trong dãy a[1]..a[i1] bằng phương pháp tìm kiếm tuần tự từ a[i1]trở về phía a[1] để tìm ra vị trí thích hợp của
a[i]. Ta xen a[i] vào vị trí này và kết quảlà dãy
277
278
a[1]..a[i] có thứ tự. Ta áp dụng cách làm này
với i = 2,3,..,n.
Ví dụ : Ta cần sắp thứ tự dãy 44 55 12 42 94
18 06 67
i=2 44: 55 12 42 94 18 06 67
i=3 44 55 : 12 42 94 18 06 67
i=4 12 44 55: 42 94 18 06 67
i=5 12 42 44 55: 94 18 06 67
i=6 12 42 44 55 94: 18 06 67
i=7 12 18 42 44 55 94: 06 67
i=8 06 12 18 42 44 55 94: 67
06 12 18 42 44 55 67 94
Trong giải thuật sau đây, ta sử dụng phần
tửcầm canh (sentine) a[0] để xác định vị trí
thích hợp của phần tử a[i] trong dãy đã có thứ
tự a[1] .. a[i-1].
Giải thuật như sau :
278
