Chọn giải thuật sắp xếp
Nguyễn Xuân Huy
Các giải thuật sắp xếp trong
Bài toán sắp xếp mảng thường được phát biểu như sau:Cho một mảng a gồm n phần tử
thuộc kiểu sắp được T, nghĩa là giữa hai phần tử xvà y bất kỳ thuộc kiểu T chỉ cóthể xảy ra
một trong ba trường hợp loại trừ nhau sau đây: Hoặc x = y,hoặc x > y hoặc x < y. Yêu cầu:
sắp lại mảng a theo một trật tự cho trước, thí dụ,sắp tăng. Trong trường hợp này, kết quả
thu được sẽ thoả tính chất sau: a[1]<= a[2]<=... <= a[n]. Việc sắp xếp phải được thực hiện
tại chỗ,tức là không được dùng thêm mảng phụ, ngoại trừ trường hợp sắp theo chỉ
dẫn.Trong trường hợp cần sắp theo chỉ dẫn, ta phải dùng mảng cd[1..n] đóng vai trò chỉdẫn
tới các phần tử của mảng a. Saukhi sắp theo chỉ dẫn, trật tự của các phần tử trong mảng a
không thay đổi, còn các chỉ dẫn trong mảng cd lần lượt trỏ tới các phần tử của a theo trật
tự tăng dẫn.
Thí dụ, nếu ta cho a[1..6] = (4, 3, 4, 8, 3, 1). Thì sau khi sắp trực tiếp mảng a tasẽ thu được:
a[1..6]= (1, 3, 3, 4, 4, 8)
Nếu sắp theo chỉ dẫn ta sẽ thu được mảng chỉ dẫn nhưsau:
cd[1..6]= (6, 2, 5, 1,3, 4)
Như vậy các chỉ dẫn cho biết phần tử thứ 6 trong a là nhỏ nhất, tiếp đến là các phầntử thứ
2, thứ 5, thứ 1 thứ 3 và cuốicùng, phần tử thứ 4 trong a là lớnnhất.
Có nhiều giải thuật sắp xếp nhanh chậm khác nhau,trong số đó đứng đầu bảng là các giải
thuật sắp nhanh đòi hỏi độ phức tạp n*log(n), bao gồm Quick Sort và HeapSort, trong đó
logarit được lấy theo cơ số 2. Giải thuật Shell Sort có độ phứctạp cỡ n
1.2
. Các giảithuật
khác như nổi bọt, xen trực tiếp... có độ phức tạp cỡ n
2
. Số người sử dụng giảithuật Quick
Sort do Hoare đề xuất có lẽ nhiều nhất, vì giải thuật này nhanh, dễcài đặt và ẩn chứa nhiều
vẻ đẹp.
Tuy nhiên, có một số trường hợp dùng các giải thuậtsắp nhanh lại không đem lại kết
quảmong muốn.

Giả thử trong một cuộc thi tài có 6 bạn tham gia làAn, Bình, Chính Điền, Thanh và Vân.
Trước khi bắt đầu cuộc thi, Ban giám khảodùng giải thuật nhanh, Quick Sort chẳng hạn, để
sắp danh sách 6 bạn theo trậttự từ điển như đã cho trong mảnh trái của bảng trên. Sau khi
thi, tức là sau khi đã biết điểm của mỗi bạn, Ban giámkhảo lại dùng Quick Sort sắp lại
danh sách các bạn theo chiều giảm dần của điểmthi. Kết quả được ghi trong mảnh phải của
bảng. Bạn hãy quan sát bảng trên xemcó điều gì không bình thường? Có đấy, trước khi
tham gia thi, bạn Bình đứngtrước bạn Điền theo trật tự từ điển. Sau khi thi, hai bạn cùng có
số điểm nhưnhau, tức là 10 điểm, vậy mà kết quả sắp xếp lại đặt bạn Điền trên bạn Bình.
Như vậy có vô lý không?Giả sử cuộc thi chỉ lấy một bạn và hệthống xét chọn được thực
hiện tự động bằng cách lấy người đầu tiên trong danhsách kết quả. Việc chọn bạn Điền có
thể dẫn đến những tranh luận nhất định. Tạisao lại có hiện tượng trên. Số là một số giải
thuật sắp xếp đã thực hiện việcđổi chỗ các phần tử trong mảng. Bạn có thể hỏi: Không đổi
chỗ các phần tử thì làm sao có thể đặt lại được phần tử theogiá trị lớn nhỏ của chúng?
Đúngvậy, ta lưu ý rằng, nói chung mỗi lần đổi chỗ hai phần tử ta chỉ có thể đặtđược một
trong hai phần tử đó vào đúng vị trí cần sắp. Phần tử bị chiếm chỗ cóthể rơi vào vị trí nào
đó. Chính vì đến chỗ mới nên phần tử bị chiếm chỗ có thểlàm đảo lộn thứ tự tự nhiên ban
đầu. Để khắc phục điều này ta chỉ đổi chỗ mỗilần hai phần tử liên tiếp nhau a[i]và a[i+1]
nếu chúng có giá trị khácnhau. Phương pháp này được gọi là tịnh tiến hay đẩy dần: ta đẩy
dần mỗi phần tửvào vị trí thích hợp. Các giải thuật sắp xếp như sắp theo phép chèn theo
mộttrật tự duyệt thích hợp và nổi bọt thực hiện việc tịnh tiến do đó chúng đảm bảo được
trật tự tự nhiên ban đầu.
Dĩ nhiên, với thí dụ trên, nếu chúng ta gọi thủ tụcQuick Sort đồng thời trên hai trường,
chẳng hạn, sắp tăng theo trật tự từ điểnvà sắp giảm theo điểm thì trật tự tự nhiên ban đầu
vẫn được tôn trọng. Tuynhiên, trong trường hợp này chúng ta phải trả giá không ít.
Kẻ yếu lênngôi
Trong số các giải thuật sắp xếp thì các giải thuậtnhư sắp theo phép chèn và giải thuật nổi
bọt đảm bảo được trật tự tự nhiên banđầu. Sau đây là một bài toán minh hoạ.
Bài toán(Mã Burrows Wheeler)
Cho xâu ký tựs[1..n] và gọi là xâu rõ. Ta mã hoá s theo các bước sau:
Bước 1. Lần lượt quay xâu s theo chiều kim đồng hồ, mỗi lần một vị trí để thuđược n xâu

thứ cấp kể cả xâu s ban đầu (xem bài Quay quay trong Tin học và nhàtrường số 4/2000)
Bước 2.Sắp tăng các xâu thu được ở bước 1 theo trật tự từ điển.
Bước 3.Tạo xâu w bằng cách ghép lần lượt các ký tự cuối của các xâu đã sắp.
Bước 4.Xác định vị trí của xâu rõ s trong dãy đã sắp, giả sử đó là d.
Cặp (w, d)được gọi là mã Burrows Wheeler của xâu rõ s. Ký hiệu BW là thủ tục mã hoá
theophương pháp trên, ta có:
BW(s) = (w,d).
a)Hãy viết thủ tục lập mãBW(s) = (w,d)
b)Hãy viết thủ tục giải mãEBW(w,d) = s
Thí dụ, với xâu s = 'btamara, thuật toán BW đực thực hiện cụ thể như sau:
Bước 1. Quay xâu. Dễ thấy rằng vì sau n lầnquay xâu ta sẽ thu lại được xâu s banđầu cho
nên ta có thể chọn chiều quay tuỳ ý. Hơn thế nữa, tổng cộng ta sẽ thuđược n xâu thứ cấp,
mỗi xâu có đúng n ký tự và có ký tự đầu tiên chính là s[i],i</I>=1..6. Ta [k] là xâu thứ
cấp thu được bằng cách lấyvòng tròn theo chiều kim đồng hồ n kýtự liên tiếp trong xâu s,
kể từ vịtrí thứ k trở đi, thí dụ, [2]= amarat.Vậy các xâu nhận được sẽ là:
1.[1] = 'tamará, 2.[6] = 'atamar',3.[5] = 'ratamá, 4.[4] = 'aratam', 5.[3]= 'maratá, 6.[2]
= 'amarat'.
Ký hiệu i.[k] cho ta biết, trước khi sắp, xâu [k] đứng thứ i trong dãy các xâu thứcấp.
Bước 2. Sắp
1.[2]='amarat', 2.[4]='aratam',3.[6]='atamar',, 4.[3]='maratá, 5.[5]= 'ratamá, 6.
[1]='tamará
Ký hiệu i.[k] cho ta biết, sau khi sắp, xâu [k] đứng thứ i trong dãy các xâu thứ cấp.
Bước 3. Tạo w
w = tmraaa
Bước 4. Xác định d
d = 6
Ta có:
BW( 'tamará ) = ( 'tmraaá , 6)
Bài giải
Để mã hoá ta sử dụng thuậttoán sắp các xâu thứ cấp đã nêu trong bài Quay quay. Ta có

thể dùng giải thuậtsắp nhanh Quick Sort theo chỉ dẫn. Cụ thể với thí dụ đã nêu, trước khi
sắp takhởi trị cho mảng chỉ dẫn là cd[1..6]= (1, 2, 3, 4, 5, 6). Sau khi sắp tathu được
cd[1..6] = ( 2, 4,6, 3, 5, 1). Nói cách khác, sau khi sắp các xâu thứcấp cd[i]= k sẽ cho biết
xâu thứcấp [k] đứng thứ i trong dãy sắp tăng của các xâu thứ cấp.
(* dat chi dan va sap nhanh cac xau thu cap*)
procedure SapS;
vari: integer;
begin
fori := 1 to n do cd[i] := i;
Qsort(1,n);
end;
(* Sap nhanh cac xau thu cap theo chi dan*)
procedure Qsort(l, r: integer);
vari, j, t, m: integer;
begin
i:= l; j := r;
m:= cd[(i+j) div 2];
while i <= j do
begin
while Sanh(cd[i], m) = -1 do inc(i);
while Sanh(cd[j], m) = 1 do dec(j);
if (i <= j) then
begin
t := cd[i];
cd[i] := cd[j];
cd[j] := t;
inc(i); dec(j);
end;
end;
ifl < j then Qsort(l,j);

ifi < r then Qsort(i,r);
end;
Saukhi sắp tăng các xâu thứ cấp để tạo xâu mã wta chỉ việc ghép các từ cuối của các xâu
thứ cấp theo trật tự đã sắp. Vì xâuthứ cấp [i] có ký tự đầu tiên là s[i] thì ký tự cuối cùng
của nó trên vòngtròn sẽ là phần tử sát trước của s[i].ta dùng hàm Pre(i) để xác định vị
trínày. Nói chung, khi duyệt các giá trị 1..ntheo vòng tròn bạn luôn nhớ cài đặt hai hàm
Next(i)cho gía trị sát sau giá trị itrên vòng tròn 1..n và hàm Pre(i) cho giá trị sát trươvs
giá trị i trên vòng tròn 1..n. Hai hàm đó như sau:
(*Cho gia tri sat sau i tren vong tron 1..n *)
function Next(i: integer): integer;
begin
ifi = n then Next := 1
else Next := i+1;
end;
(* Cho gia tri sat truoc i tren vong tron1..n *)
function Pre(i: integer): integer;
begin
ifi = 1 then Pre := n
else Pre := i-1;
end;
Bước cuối cùng của quá trìnhmã hoá là xác định vị trí d của xâu rõ strong trật tự đã sắp
của các xâu thứ cấp. Để làm việc này ta chỉ cần duyệt mảngchỉ dẫn để tìm vị trí d sao cho
cd[d]=1, vì [1] chính là xâu rõ ban đầu.
Thủtục mã hoá BW(s)=(w,d) khi đó sẽ như sau:
(* Ma hoa BW(s) = (w,d) *)
procedure BW;
vari: integer;
begin
n:= length(s);
Saps;

w:= '';
fori := 1 to n do
w:= w + s[Pre(cd[i])];
fori := 1 to n do
if cd[i] = 1 then
begin
d := i;
exit;
end;
end;