CÁC THUẬT TOÁN SẮP XẾP
1. Giới thiệu bài toán
Ta sẽ xem xét các thuật toán để sắp xếp một tập các bản ghi theo giá trị của một trường nào đó. Thứ
tự sắp xếp là một quy luật đã được định nghĩa rõ ràng: thường là thứ tự tăng dần (hay giảm dần) đối
với dãy số, thứ tự từ điển đối với các chữ, ...
Bài toán đặt ra ở đây là sắp xếp đối với một tập gồm n bản ghi r
1
, r
2
, ..., r
n
. Tuy nhiên không phải toàn
bộ các trường dữ liệu trong bản ghi đều được xét đến trong quá trình sắp xếp mà chỉ một hoặc vài
trường nào đó thôi. Trường như vậy gọi là trường khoá. Sắp xếp sẽ được tiến hành dựa vào giá trị của
khoá này. Do khoá có vai trò đặc biệt như vậy nên sau này khi trình bày các thuật toán hay trong các
ví dụ minh hoạ, ta sẽ coi nó như đại diện cho bản ghi và để đơn giản hơn ta chỉ nói đến khoá thôi.
Thực ra phép đổi chỗ được tác động lên các bản ghi và ở đây ta cũng chỉ nói đến phép đổi chỗ với
các khoá. Giá trị khoá có thể là số hay chữ và thứ tự sắp xếp cũng được quy định tương ứng với khoá.
Ở đây để minh hoạ cho các thuật toán sắp xếp ta sẽ coi giá trị khoá là số và thứ tự sắp xếp là tăng
dần.
Bây giờ bài toán sắp xếp được đặt ra đơn giản nhưng vẫn không làm mất tính tổng quát như sau: cho
một dãy các khoá a
1
, a
2
, ..., a
n
là các số nguyên (tương ứng với các bản ghi r
1
, r
2

rút lần lượt với các lá bài đã có ở trên tay để tìm ra “chỗ” thích hợp và “chèn” nó vào chỗ đó.
1
Dựa vào nguyên tắc trên ta có thể xây dựng thuật toán sắp xếp như sau: lúc đầu dãy coi như chỉ có
một khoá là a
1
đã được sắp xếp. Xét thêm a
2
, so sánh nó với a
1
để xác định chỗ chèn nó vào, sau đó ta
có một dãy gồm hai khoá đã được sắp xếp. Cứ tiếp tục như vậy đối với a
3
, a
4
, ... Cuối cùng sau khi
xét xong a
n
thì dãy khoá đã được sắp xếp hoàn toàn.
Hình ảnh của thuật toán sắp xếp kiểu thêm dần với dãy khóa 42, 23, 74, 11, 65, 58 được minh hoạ
qua bảng sau:
Lượt 1 2 3 4 5 6
Khoá đưa vào 42 23 74 11 65 58
1 42 23 23 11 11 11
2 42 42 23 23 23
3 74 42 42 42
4 74 65 58
5 74 65
6 74
Thủ tục sắp xếp kiểu thêm dần được cài đặt như sau:
procedure insertion;

4 11 74 58 58 58 58
5 65 58 74 65 65 65
2
6 58 65 65 74 74 74
Thủ tục sắp xếp nổi bọt được cài đặt như sau:
procedure bubble;
var
i, j, t : integer;
begin
for i := 1 to n-1 do
for j := n downto i+1 do
if a[j] < a[j-1] then
begin
t := a[j]; a[j] := a[j-1]; a[j-1] := t;
end;
end;
d. Phân tích tính hiệu quả của các thuật toán sắp xếp đơn giản
Cả ba thuật toán đều có độ phức tạp thời gian cỡ O(n
2
) và độ phức tạp bộ nhớ là O(n). Vì vậy, ta sẽ
lấy thuật toán sắp xếp kiểu lựa chọn đại diện cho các thuật toán sắp xếp đơn giản để thực hiện với các
bộ test sau trên máy tính PentiumIV 3.0Ghz.
Để thuật tiện cho quá trình test với dữ liệu lớn, ta có chút thay đổi một chút khi cài đặt là thay tất cả
các biến kiểu interger thành các biến kiểu longint. Sau đây là bảng kết quả khi thực hiện thuật toán:
TT n Mô tả Thời gian (giây)
1 10 Kích thước nhỏ (tạo bằng tay) 0.00
2 100 Kích thước nhỏ (tạo ngẫu nhiên) 0.00
3 1.000 Kích thước nhỏ (tạo ngẫu nhiên) 0.00
4 10.000 Kích thước trung bình (tạo ngẫu nhiên) 0.61
5 15.000 Kích thước trung bình (tạo ngẫu nhiên) 1.32

• Chọn khoá đứng giữa dãy làm khoá chốt x := a[(l+r) div 2]; (l, r là 2 biến chỉ số đầu, cuối của
một phân đoạn)
• Dùng 2 biến chỉ số i, j để phát hiện ra hai khoá cần đổi chỗ. Khởi tạo giá trị ban đầu cho hai
biến này: i := l; j := r;
Bước 2:
• Duyệt từ trái sang phải để tìm chỉ số i sao cho a[i] >= x.
• Duyệt từ phải sang trái để tìm chỉ số j sao cho a[j] <= x.
• Nếu i <= j thì:
Đổi chỗ a[i] và a[j].
i := i + 1.
j := j - 1.
Lặp lại bước 2 cho đến khi i > j.
Bước 3:
• Nếu l < j thì lặp lại bước 1, 2 cho phân đoạn a[l], ..., a[j].
• Nếu i < r thì lặp lại bước 1, 2 cho phân đoạn a[i], ..., a[r].
Hình ảnh sau đây minh họa diễn biến trong lượt đầu của thuật toán với dãy số: 42, 23, 65, 74, 11, 58.
Khóa chốt x = 65.
i↓ j↓
42 23 65 74 11 58
↑_____________↑
i↓ j↓
42 23 58 74 11 65
↑___↑
j↓ i↓
42 23 58 11 74 65
Dãy khoá được chia làm hai phân đoạn: (42, 23, 58 11) và (74, 65). Công việc tiếp theo lại tiến hành
lần lượt trên hai phân đoạn mới này.
Cài đặt:
procedure qSort(l, r : integer);
var

xếp đơn giản để tiện theo dõi và so sánh:
TT n Mô tả
Thời gian (giây)
Đơn giản Phân đoạn
1 10 Kích thước nhỏ (tạo bằng tay) 0.00 0.00
2 100 Kích thước nhỏ (tạo ngẫu nhiên) 0.00 0.00
3 1.000 Kích thước nhỏ (tạo ngẫu nhiên) 0.00 0.00
4 10.000 Kích thước trung bình (tạo ngẫu nhiên) 0.61 0.01
5 15.000 Kích thước trung bình (tạo ngẫu nhiên) 1.32 0.02
6 50.000 Kích thước trung bình (tạo ngẫu nhiên) 14.21 0.05
7 100.000
Kích thước lớn (tạo có chủ định: nửa đầu
giảm, nửa sau tăng – trường hợp xấu của
Quick sort)
27.42 6.25
8 500.000 Kích thước lớn (tạo ngẫu nhiên) 1426.07 0.57
9 1.000.000 Kích thước lớn (tạo ngẫu nhiên) Quá lâu 1.11
10 1.000.000
Kích thước lớn (tạo có chủ định: nửa đầu
tăng, nửa sau giảm – trường hợp xấu của
Quick sort)
Quá lâu Quá lâu
4. Thuật toán sắp xếp kiểu vun đống (Heap sort)
Sắp xếp kiểu vun đống được chia làm 2 giai đoạn:
• Giai đoạn đầu người ta coi dãy khoá cần sắp như là cấu trúc của một cây nhị phân hoàn chỉnh:
nếu i chỉ vị trí nút con thì (i div 2) chỉ vị trí nút cha, còn nếu j chỉ vị trí nút cha thì 2.j và 2.j + 1
chỉ nút con. Sau đó cây nhị phân biểu diễn dãy khoá này được biến đổi để trở thành một đống. ở
đây đống là một cây nhị phân hoàn chỉnh mà mỗi nút được gán cho một giá trị khoá sao cho khoá
của nút cha bao giờ cũng lớn hơn khoá của nút con nó. Do đó khoá của nút gốc của đống chính là
khoá lớn nhất (khoá trội) so với mọi khoá trên cây. Giai đoạn này gọi là giai đoạn tạo đống.

{ 1. Tạo đống }
for i := (n div 2) downto 1 do adjust(i, n);
{ 2. Sắp xếp }
for i := n downto 2 do
begin
{ đưa khoá trội về vị trí thực của nó }
t := a[1]; a[1] := a[i]; a[i] := t;
{ vun các khoá còn lại thành đống }
adjust(1, i-1);
end;
end;
Ví dụ sau đây minh họa các bước của thuật toán vun đống với dãy khoá 42, 23, 74, 11, 65, 58.
Bước 1. Tạo đống
6
i = 3
42
23
11
65
74
58
42
23
11 65
74
58
i = 1
74
65
11 23

7 100.000
Kích thước lớn (tạo có chủ định: nửa
đầu giảm, nửa sau tăng – trường hợp
xấu của Quick sort)
27.42 6.25 0.11
8 500.000 Kích thước lớn (tạo ngẫu nhiên) 1426.07 0.57 0.70
9 1.000.000 Kích thước lớn (tạo ngẫu nhiên) Quá lâu 1.11 1.45
10 1.000.000
Kích thước lớn (tạo có chủ định: nửa
đầu tăng, nửa sau giảm – trường hợp
xấu của Quick sort)
Quá lâu Quá lâu 1.09
7
65
42
11 23
58
74
i = 6
58
42
11 65
23
74
i = 5
42
11
58 65
23
74