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.

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ó

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;