Giáo trình Mô đun Cấu trúc dữ liệu và giải thuật - Lập trình máy tính

then Exit; {Nếu đoạn chỉ có ≤ 1 phần tử thì không phải làm gì cả}
Key := kRandom(H-L+1)+L; {Chọn một khoá ngẫu nhiên trong đoạn làm khoá chốt}
i := L; j := H; {i := vị trí đầu đoạn; j := vị trí cuối đoạn}
repeat
while ki < Key do i := i + 1; {Tìm từ đầu đoạn khoá ≥ khoá chốt}
while kj > Key do j := j - 1; {Tìm từ cuối đoạn khoá ≤ khoá chốt}
{Đến đây ta tìm được hai khoá ki và kj mà ki ≥ key ≥ kj}
if i ≤ j then
begin
if i < j then {Nếu chỉ số i đứng trước chỉ số j thì đảo giá trị hai khoá ki và kj}
 {Sau phép đảo này ta có: ki ≤ key ≤ kj }
i := i + 1; j := j - 1;
end;
until i > j;
Partition(L, j); Partition(i, H); {Sắp xếp hai đoạn con mới tạo ra}
end;
begin
Partition(1, n);
end;
Ta thử phân tích xem tại sao đoạn chương trình trên hoạt động đúng: Xét vòng lặp repeat...until trong lần lặp đầu tiên, vòng lặp while thứ nhất chắc chắn sẽ tìm được khoá ki ≥ khoá chốt bởi chắc chắn tồn tại trong đoạn một khoá bằng khóa chốt. Tương tự như vậy, vòng lặp while thứ hai chắc chắn tìm được khoá kj ≤ khoá chốt. Nếu như khoá ki đứng trước khoá kj thì ta đảo giá trị hai khoá, tăng i và giảm j. Khi đó ta có nhận xét rằng mọi khoá đứng trước vị trí i sẽ phải ≤ khoá chốt và mọi khoá đứng sau vị trí j sẽ phải ≥ khoá chốt. kL ... ki ... kj ... kH ≤ khoá chốt ≥ khoá chốt
Điều này đảm bảo cho vòng lặp repeat...until tại bước sau, hai vòng lặp while...do bên trong chắc chắn lại tìm được hai khoá ki và kj mà ki ≥ khoá chốt ≥ kj, nếu khoá ki đứng trước khoá kj thì lại đảo giá trị của chúng, cho i tiến về cuối một bước và j lùi về đầu một bước. Vậy thì quá trình hoán chuyển phần tử trong vòng lặp repeat...until sẽ đảm bảo tại mỗi bước: 
Hai vòng lặp while...do bên trong luôn tìm được hai khoá ki, kj mà ki ≥ khoá chốt ≥ kj. Không có trường hợp hai chỉ số i, j chạy ra ngoài đoạn (luôn luôn có L ≤ i, j ≤ H).
Sau mỗi phép hoán chuyển, mọi khoá đứng trước vị trí i luôn ≤ khoá chốt và mọi khoá đứng sau vị trí j luôn ≥ khoá chốt.
Vòng lặp repeat ...until sẽ kết thúc khi mà chỉ số i đứng phía sau chỉ số j.
≥ khoá chốt kL ... kj ki ... kH ≤ khoá chốt
Theo những nhận xét trên, nếu có một khoá nằm giữa kj và ki thì khoá đó phải đúng bằng khoá chốt và nó đã được đặt ở vị trí đúng của nó, nên có thể bỏ qua khoá này mà chỉ xét hai đoạn ở hai đầu.
Công việc còn lại là gọi đệ quy để làm tiếp với đoạn từ kL tới kj và đoạn từ ki tới kH. Hai đoạn này ngắn hơn đoạn đang xét bởi vì L ≤ j < i ≤ H. Vậy thuật toán không bao giờ bị rơi vào quá trình vô hạn mà sẽ dừng và cho kết quả đúng đắn. Xét về độ phức tạp tính toán:
Trường hợp tồi tệ nhất, là khi chọn khoá chốt, ta chọn phải khoá nhỏ nhất hay lớn nhất trong đoạn, khi đó phép phân đoạn sẽ chia thành một đoạn gồm n - 1 phần tử và đoạn còn lại chỉ có 1 phần tử. Có thể chứng minh trong trường hợp này, thời gian thực hiện giải thuật T(n) = O(n2)
Trường hợp tốt nhất, phép phân đoạn tại mỗi bước sẽ chia được thành hai đoạn bằng nhau. Tức là khi chọn khoá chốt, ta chọn đúng trung vị của dãy khoá. Có thể chứng minh trong trường hợp này, thời gian thực hiện giải thuật T(n) = O(nlog2n)
Trường hợp các khoá được phân bố ngẫu nhiên, thì trung bình thời gian thực hiện giải thuật cũng là T(n) = O(nlog2n). Việc tính toán chi tiết, đặc biệt là khi xác định T(n) trung bình, phải dùng các công cụ toán phức tạp, ta chỉ công nhận những kết quả trên.
Chú ý: Vài cải tiến của Quick Sort
Việc chọn chốt cho phép phân đoạn quyết định hiệu quả của Quick Sort, nếu chọn chốt không tốt, rất có thể việc phân đoạn bị suy biến thành trường hợp xấu khiến Quick Sort hoạt động chậm và tràn ngăn xếp chương trình con khi gặp phải dây chuyền đệ qui quá dài. Một cải tiến sau có thể khắc phục được hiện tượng tràn ngăn xếp nhưng cũng hết sức chậm trong trường hợp xấu, kỹ thuật này khi đã phân được [L, H] được hai đoạn con [L, j] và [i, H] thì chỉ gọi đệ quy để tiếp tục đối với đoạn ngắn, và lặp lại quá trình phân đoạn đối với đoạn dài.
procedure QuickSort;
procedure Partition(L, H: Integer); {Sắp xếp đoạn từ kL, kL+1, ..., kH}
var
i, j: Integer;
begin
repeat
if L ≥ H then Exit;
if then
begin
Partition(L, j); L := i;
end
else
begin
Partition(i, R); R := j;
end;
until False;
end;
begin
Partition(1, n);
end;
Cải tiến thứ hai đối với Quick Sort là quá trình phân đoạn nên chỉ làm đến một mức nào đó, đến khi đoạn đang xét có độ dài ≤ M (M là một số nguyên tự chọn nằm trong khoảng từ 9 tới 25) thì không phân đoạn tiếp mà nên áp dụng thuật toán sắp xếp kiểu chèn. Cải tiến thứ ba của Quick Sort là: Nên lấy trung vị của một dãy con trong đoạn để làm chốt, (trung vị của một dãy n phần tử là phần tử đứng thứ n / 2 khi sắp thứ tự). Cách chọn được đánh giá cao nhất là chọn trung vị của ba phần tử đầu, giữa và cuối đoạn.
Cuối cùng, ta có nhận xét: Quick Sort là một công cụ sắp xếp mạnh, chỉ có điều khó chịu gặp phải là trường hợp suy biến của Quick Sort (quá trình phân đoạn chia thành một dãy rất ngắn và một dãy rất dài). Và điều này trên phương diện lý thuyết là không thể khắc phục được: Ví dụ với n = 10000.
- Nếu như chọn chốt là khoá đầu đoạn (Thay dòng chọn khoá chốt bằng Key := kL) hay chọn chốt là khoá cuối đoạn (Thay bằng Key := kH) thì với dãy sau, chương trình hoạt động rất chậm:
(1, 2, 3, 4, 5, ..., 9999, 10000)
- Nếu như chọn chốt là khoá giữa đoạn (Thay dòng chọn khoá chốt bằng Key := k(L+H) div 2) thì với dãy sau, chương trình cũng rất chậm:
(1, 2, ..., 4999, 5000, 5000, 4999, ..., 2, 1)
- Trong trường hợp chọn chốt là trung vị dãy con hay chọn chốt ngẫu nhiên, thật khó có thể tìm ra một bộ dữ liệu khiến cho Quick Sort hoạt động chậm. Nhưng ta cũng cần hiểu rằng với mọi chiến lược chọn chốt, trong 10000! dãy hoán vị của dãy (1, 2, ... 10000) thế nào cũng có một dãy làm Quick Sort bị suy biến, tuy nhiên trong trường hợp chọn chốt ngẫu nhiên, xác suất xảy ra dãy này quá nhỏ tới mức ta không cần phải tính đến, như vậy khi đã chọn chốt ngẫu nhiên thì ta không cần phải quan tâm tới ngăn xếp đệ quy, không cần quan tâm tới kỹ thuật khử đệ quy và vấn đề suy biến của Quick Sort.
2.5. Thuật toán sắp xếp trộn 
2.5.1. Phép trộn 2 đường
Phép trộn 2 đường là phép hợp nhất hai dãy khoá đã sắp xếp để ghép lại thành một dãy khoá có kích thước bằng tổng kích thước của hai dãy khoá ban đầu và dãy khoá tạo thành cũng có thứ tự sắp xếp. Nguyên tắc thực hiện của nó khá đơn giản: so sánh hai khoá đứng đầu hai dãy, chọn ra khoá nhỏ nhất và đưa nó vào miền sắp xếp (một dãy khoá phụ có kích thước bằng tổng kích thước hai dãy khoá ban đầu) ở vị trí thích hợp. Sau đó, khoá này bị loại ra khỏi dãy khoá chứa nó. Quá trình tiếp tục cho tới khi một trong hai dãy khoá đã cạn, khi đó chỉ cần chuyển toàn bộ dãy khoá còn lại ra miền sắp xếp là xong.
Ví dụ: Với hai dãy khoá: (1, 3, 10, 11) và (2, 4, 9)
Dãy 1 Dãy 2 Khoá nhỏ nhất trong 2 dãy Miền sắp xếp
(1, 3, 10, 11) (2, 4, 9) 1 
(1)
(3, 10, 11) (2, 4, 9) 2 
(1, 2)
(3, 10, 11) (4, 9) 3 
(1, 2, 3)
(10, 11) (4, 9) 4 
(1, 2, 3, 4)
(10, 11) (9) 9 
(1, 2, 3, 4, 9)
(10, 11) ∅ Dãy 2 là ∅, đưa nốt dãy 1 vào miền sắp xếp (1, 2, 3, 4, 9, 10, 11)
2.5.2. Sắp xếp bằng trộn 2 đường trực tiếp
Ta có thể coi mỗi khoá trong dãy khoá k1, k2, ..., kn là một mạch với độ dài 1, các mạch trong dãy đã được sắp xếp rồi:
3 6 5 4 9 8 1 0 2 7
Trộn hai mạch liên tiếp lại thành một mạch có độ dài 2, ta lại được dãy gồm các mạch đã được sắp:
3 6 4 5 8 9 0 1 2 7
Cứ trộn hai mạch liên tiếp, ta được một mạch độ dài lớn hơn, số mạch trong dãy sẽ giảm dần xuống:
3 4 5 6 0 1 8 9 2 7
0 1 3 4 5 6 8 9 2 7
0 1 2 3 4 5 6 7 8 9
Để tiến hành thuật toán sắp xếp trộn hai đường trực tiếp, ta viết các thủ tục.
- Thủ tục Merge(var x, y: TArray; a, b, c: Integer); thủ tục này trộn mạch x[a], x[a+1], ..., x[b] với mạch x[b+1], x[b+2] ..., x[c] để được mạch y[a], y[a+1], ..., y[c].
- Thủ tục MergeByLength(var x, y: TArray; len: Integer); thủ tục này trộn lần lượt các cặp mạch theo thứ tự:
+ Trộn mạch x[1]...x[len] và x[len+1]...x[2len] thành mạch y[1]...y[2len].
+ Trộn mạch x[2len+1]...x[3len] và x[3len+1] ...x[4len] thành mạch y[2len+1]...y[4len].
...
Lưu ý rằng đến cuối cùng ta có thể gặp hai trường hợp: Hoặc còn lại hai mạch mà mạch thứ hai có độ dài < len. Hoặc chỉ còn lại một mạch. Trường hợp thứ nhất ta phải quản lý chính xác các chỉ số để thực hiện phép trộn, còn trường hợp thứ hai thì không được quên thao tác đưa thẳng mạch duy nhất còn lại sang dãy y.
• Cuối cùng là thủ tục MergeSort, thủ tục này cần một dãy khoá phụ t1, t2, ..., tn. Trước hết ta gọi MergeByLength(k, t, 1) để trộn hai phần tử liên tiếp của k thành một mạch trong t, sau đó lại gọi MergeByLength(t, k, 2) để trộn hai mạch liên tiếp trong t thành một mạch trong k, rồi lại gọi MergeByLength(k, t, 4) để trộn hai mạch liên tiếp trong k thành một mạch trong t ...Như vậy k và t được sử dụng với vai trò luân phiên: một dãy chứa các mạch và một dãy dùng để trộn các cặp mạch liên tiếp để được mạch lớn hơn.
procedure MergeSort;
var
t: TArray; {Dãy khoá phụ}
len: Integer;
Flag: Boolean; {Flag = True: trộn các mạch trong k vào t; Flag = False: trộn các mạch trong t vào k}
procedure Merge(var X, Y: TArray; a, b, c: Integer);{Trộn Xa...Xb và Xb+1...Xc}
var
i, j, p: Integer;
begin
{Chỉ số p chạy trong miền sắp xếp, i chạy theo mạch thứ nhất, j chạy theo mạch thứ hai}
p := a; i := a; j := b + 1;
while (i ≤ b) and (j ≤ c) then {Chừng nào cả hai mạch đều chưa xét hết}
begin
if Xi ≤ Xj then {So sánh hai phần tử nhỏ nhất trong hai mạch mà chưa bị đưa vào miền sắp xếp}
begin
Yp := Xi; i := i + 1; {Đưa xi vào miền sắp xếp và cho i chạy}
end
else
begin
Yp := Xj; j := j + 1; {Đưa xj vào miền sắp xếp và cho j chạy}
end;
p := p + 1;
end;
if i ≤ b then {Mạch 2 hết trước}
(Yp, Yp+1, ..., Yc) := (Xi, Xi+1, ..., Xb) {Đưa phần cuối của mạch 1 vào miến sắp xếp}
else {Mạch 1 hết trước}
(Yp, Yp+1, ..., Yc) := (Xj, Xj+1, ..., Xc); {Đưa phần cuối của mạch 2 vào miến sắp xếp}
end;
procedure MergeByLength(var X, Y: TArray; len: Integer);
begin
a := 1; b := len; c := 2 * len;
while c ≤ n do {Trộn hai mạch xa...xb và xb+1...xc đều có độ dài len}
begin
Merge(X, Y, a, b, c);
{Dịch các chỉ số a, b, c về sau 2.len vị trí}
a := a + 2 * len; b := b + 2 * len; c := c + 2 * len;
end;
if b < n then Merge(X, Y, a, b, n) {Còn lại hai mạch mà mạch thứ hai có độ dài ngắn hơn len}
else
if a ≤ n then {Còn lại một mạch}
(Ya, Ya+1, ..., Yn) := (Xa, Xa+1, ..., Xn); {Đưa thẳng mạch đó sang miền y}
end;
begin {Thuật toán sắp xếp trộn}
Flag := True;
len := 1;
while len < n do
begin
if Flag then MergeByLength(k, t, len)
else MergeByLength(t, k, len);
len := len * 2;
Flag := not Flag; {Đảo cờ để luân phiên vai trò của k và t}
end;
if not Flag then k := t; {Nếu kết quả cuối cùng đang nằm trong t thì sao chép kết quả vào k}
end;
Về độ phức tạp của thuật toán, ta thấy rằng trong thủ tục Merge, phép toán tích cực là thao tác đưa một khoá vào miền sắp xếp. Mỗi lần gọi thủ tục MergeByLength, tất cả các phần tử trong dãy khoá được chuyển hoàn toàn sang miền sắp xếp, nên độ phức tạp của thủ tục MergeByLength là O(n).
Thủ tục MergeSort có vòng lặp thực hiện không quá log2n + 1 lời gọi MergeByLength bởi biến len sẽ được tăng theo cấp số nhân công bội 2. Từ đó suy ra độ phức tạp của MergeSort là O(nlog2n) bất chấp trạng thái dữ liệu vào.
Cùng là những thuật toán sắp xếp tổng quát với độ phức tạp trung bình như nhau, nhưng không giống như QuickSort hay HeapSort, MergeSort có tính ổn định. Nhược điểm của MergeSort là nó phải dùng thêm một vùng nhớ để chứa dãy khoá phụ có kích thước bằng dãy khoá ban đầu.
Người ta còn có thể lợi dụng được trạng thái dữ liệu vào để khiến MergeSort chạy nhanh hơn: ngay từ đầu, ta không coi mỗi phần tử của dãy khoá là một mạch mà coi những đoạn đã được sắp trong dãy khoá là một mạch. Bởi một dãy khoá bất kỳ có thể coi là gồm các mạch đã sắp xếp nằm liên tiếp nhau. Khi đó người ta gọi phương pháp này là phương pháp trộn hai đường tự nhiên.
Tổng quát hơn nữa, thay vì phép trộn hai mạch, người ta có thể sử dụng phép trộn k mạch, khi đó ta được thuật toán sắp xếp trộn k đường.
3. Các phương pháp tìm kiếm
3.1. Tìm kiếm tuần tự (Sequential search)
Tìm kiếm tuần tự là một kỹ thuật tìm kiếm đơn giản. Nội dung của nó như sau: Bắt đầu từ bản ghi đầu tiên, lần lượt so sánh khoá tìm kiếm với khoá tương ứng của các bản ghi trong danh sách, cho tới khi tìm thấy bản ghi mong muốn hoặc đã duyệt hết danh sách mà chưa thấy {Tìm kiếm tuần tự trên dãy khoá k1, k2, ..., kn; hàm này thử tìm xem trong dãy có khoá nào = X không, nếu thấy nó trả về chỉ số của khoá ấy, nếu không thấy nó trả về 0. Có sử dụng một khoá phụ kn+1 được gán giá trị = X}
function SequentialSearch(X: TKey): Integer;
var
i: Integer;
begin
i := 1;
while (i <= n) and (ki ≠ X) do i := i + 1;
if i = n + 1 then SequentialSearch := 0
else SequentialSearch := i;
end;
Dễ thấy rằng độ phức tạp của thuật toán tìm kiếm tuần tự trong trường hợp tốt nhất là O(1), trong trường hợp xấu nhất là O(n) và trong trường hợp trung bình cũng là O(n).
3.2. Tìm kiếm nhị phân (Binary search)
Phép tìm kiếm nhị phân có thể áp dụng trên dãy khoá đã có thứ tự: k1 ≤k2 ≤... ≤kn.
Giả sử ta cần tìm trong đoạn kinf, kinf+1, ..., ksup với khoá tìm kiếm là X, trước hết ta xét khoá nằm giữa dãy kmedian với median = (inf + sup) div 2;
- Nếu kmedian < X thì có nghĩa là đoạn từ kinf tới kmedian chỉ chứa toàn khoá < X, ta tiến hành tìm kiếm tiếp với đoạn từ kmedian + 1 tới ksup.
- Nếu kmedian > X thì có nghĩa là đoạn từ kmedian tới ksup chỉ chứa toàn khoá > X, ta tiến hành tìm kiếm tiếp với đoạn từ kinf tới kmedian - 1.
- Nếu kmedian = X thì việc tìm kiếm thành công (kết thúc quá trình tìm kiếm).
Quá trình tìm kiếm sẽ thất bại nếu đến một bước nào đó, đoạn tìm kiếm là rỗng (inf > sup). {Tìm kiếm nhị phân trên dãy khoá k1 ≤k2 ≤... ≤kn; hàm này thử tìm xem trong dãy có khoá nào = X không, nếu thấy nó trả về chỉ số của khoá ấy, nếu không thấy nó trả về 0}
function BinarySearch(X: TKey): Integer;
var
inf, sup, median: Integer;
begin
inf := 1; sup := n;
while inf ≤ sup do
begin
median := (inf + sup) div 2;
if kmedian = X then
begin
BinarySearch := median;
Exit;
end;
if kmedian < X then inf := median + 1
else sup := median - 1;
end;
BinarySearch := 0;
end;
Người ta đã chứng minh được độ phức tạp tính toán của thuật toán tìm kiếm nhị phân trong trường hợp tốt nhất là O(1), trong trường hợp xấu nhất là O(log2n) và trong trường hợp trung bình cũng là O(log2n). Tuy nhiên, ta không nên quên rằng trước khi sử dụng tìm kiếm nhị phân, dãy khoá phải được sắp xếp rồi, tức là thời gian chi phí cho việc sắp xếp cũng phải tính đến. Nếu dãy khoá luôn luôn biến động bởi phép bổ sung hay loại bớt đi thì lúc đó chi phí cho sắp xếp lại nổi lên rất rõ làm bộc lộ nhược điểm của phương pháp này.
TÀI LIỆU THAM KHẢO
1. ROBERT SEDGEWICK, Algorithms, Addison-Wesley Publishing Company, năm 1990.
2. PTS Đinh Mạnh Tường, Giáo trình Cấu trúc dữ liệu và giải thuật, NXB Đại học Quốc gia, năm 2000.
3. Lê Minh Hoàng, Cấu trúc dữ liệu và giải thuật, năm 2003.