MỘT SỐ THUẬT TOÁN SẮP XẾP
Bài to¸n
Cho mảng X chứa n số nguyên: X(1), X(2), ..., X(n). Hãy sắp
xếp lại mảng X theo thứ tự không giảm.
6.1. S¾p xÕp chän
Thuật toán này được gọi là thuật toán sắp xếp chọn hay sắp xếp
tuần tự .
Mô tả
Input:Dãy X(1), X(2), ...., X(n)
Output: Dãy X(1), X(2), ...., X(n) không giảm;
For i = 1 to n –1
• X(k) = min { X(i), X(i+1), X(i+2),..., X(n)};
• If k > i Then X(k) :=: X(i);
Chi tiết:
For i:=1 to n-1 do
a) k:=i;
b) For j:=i+1 to n do If X(j)< X(k) then k:=j;
c) Đổi_Chỗ(X(i),X(k));
Ví dụ: Cần sắp xếp dãy có 10 phần tử
13, 22, 30, 14, 21, 5, 21, 12, 15, 19
1. min {x
1
,...,x
10
} = 5 = x
6
. Đổi chỗ x
1
và x
6
, được:

5 , 22, 30, 14, 21, 13 , 21, 12, 15, 19
2. min {x
2
,...,x
10
} = 12 = x
8
. Đổi chỗ x
2
và x
8
, được:
5, 12 , 30, 14, 21, 13, 21, 22 , 15, 19
3. min {x
3
,...,x
10
} = 13 = x
6
. Đổi chỗ x
3
và x
6
, được:
5, 12, 13 , 14, 21, 30 , 21, 22, 15, 19
4. min {x
4
,...,x
10
} = 14 = x

4
. Không đổi chỗ:
5, 12, 13, 14 , 21, 30, 21, 22, 15, 19
5. min {x
5
,...,x
10
} = 15 = x
9
. Đổi chỗ x
5
và x
9
, được:
5, 12, 13, 14, 15 , 30, 21, 22, 21 , 19
6. min {x
6
,...,x
10
} = 19 = x
10
. Đổi chỗ x
6
và x
10
, được:
5, 12, 13, 14, 15, 19, 21, 22, 21, 30
7. min {x
7
,...,x

10
} = 21 = x
7
. Không đổi chỗ:
5, 12, 13, 14, 15, 19, 21 , 22, 21, 30
8. min {x
8
,...,x
10
} = 21 = x
9
. Đổi chỗ x
8
và x
9
, được:
1
5, 12, 13, 14, 15, 19, 21, 21 , 22 , 30
9. min {x9, x
10
} = 22 = x
9
. Không đổi chỗ:
5, 12, 13, 14, 15, 19, 21, 21, 22 , 30
6.2. S¾p xếp chÌn
1) Giả sử có phần đầu của mảng là B(i-1) = { X(1),...,X(i-1) } đã
được sắp xếp không giảm. Trong mọi trường hợp, luôn có thể
coi B(1) = { X(1) } là đã được sắp xếp không giảm.
2) Kiểm tra đến phần tử X(i); Tìm vị trí thích hợp của X(i) trong
dãy B(i-1) và chèn X(i) vào vị trí để được dãy B(i) =

{X(1),...,X(i-1), X(i) } không giảm.
3) Sau bước 2) dãy mới B(i) = { X'(1),...,X'(i-1),X'(i) } cũng
không giảm;
4) Lặp lại thủ tục trên với X(i+1), ... cho đến khi i = n;
Nhận xét:
− Bước 1) có thể bắt đầu với B(1):= { X(1) }
− Kỹ thuật tìm vị trí “thích hợp” của X(i) trong dãy B(i-1) và
chèn X(i) vào vị trí để có thể được thực hiện như sau:
• Lưu giá trị của X(i) vào một biến tg;
• So sánh giá trị của biến tg với các phần tử của B(i-1), bắt
đầu từ X(i-1). Nếu tg < X(i-1) thì i không phải là chỗ của
X(i), gán X(i):=X(i-1);
• Tiếp tục so sánh tg với X(i-2); nếu tg < X(i-2) thì i-1
chưa phải là chỗ của X(i). Gán X(i-1):=X(i-2). Các thao
tác này nhằm chuẩn bị chỗ cho X(i) sau này.
• Tiếp tục quá trình trên cho đến khi gặp j đầu tiên mà tg
> X(j) thì dừng lại: Vị trí của tg là j+1. Thực hiện phép
gán X(j+1) := tg;
Ví dụ, xét dãy
1 2 3 4 5 6 7 8 9 10 11
X = 1, 3, 5, 7, 8, 9, 12, 4, 5, 6, 2
B(7) = <1, 3, 5, 7, 8, 9, 12> ,
Xét i = 8,
Đặt j = i-1 = 7
Đổi dần tg = 4 lùi về phía trước; sau các bước
X = 1, 3, 5, 7, 8, 9, 12 , 12, 5, 6, 2,
j=6
X = 1, 3, 5, 7, 8, 9 , 9, 12, 5, 6, 2,
j=5
X = 1, 3, 5, 7, 8 , 8, 9, 12, 5, 6, 2,

j=4
2
X = 1, 3, 5, 7 , 7, 8, 9, 12, 5, 6, 2,
j=3
X = 1, 3, 5 , 5, 7, 8, 9, 12, 5, 6, 2,
j=2
Tại bước này j=2. Gán X(j+1) := tg => X(3) = 4. Kết quả:
X = 1, 3, 4, 5, 7, 8, 9, 12, 5, 6, 2
Input:Dãy X(1), X(2), ...., X(n)
Output: Dãy X(1), X(2), ...., X(n) không giảm;
Chi tiết:
− Bắt đầu với B(1) = { X(1) };
− Xây dựng các B(i) với i = 2,3,...n như sau:
For i:=2 to n do
1) tg := X(i);
2) j := i - 1;
3) While (tg < X(j)) and (j>0) do
a) X(j+1):= X(j);
b) j := j-1;
4) X(j+1):=tg;
6.3. S¾p xếp nổi bät (Bubble Sort)
Về cơ bản thuật toán sắp xếp nổi bọt gần giống với thuật toán sắp xếp
tuần tự. Điểm khác biệt là ở chỗ trong mỗi bước lặp để tìm giá trị
min trong dãy X(i), X(i+1), X(i+2),..., X(n) là xuất phát từ dưới lên,
so sánh từng cặp một, nếu phần tử đứng dưới X(j+1) mà nhỏ hơn so
với phần tử đứng trên X(j) thì đổi chỗ chúng cho nhau.
Với i=1 đến n -1
Với j=n đến i+1 nếu X(j) < X(j-1) thì đổi chỗ ( X(j),
X(j-1) )
Dãy X(1),..., X(n) đã được sắp xếp không giảm.

Ví dụ: Cần sắp xếp dãy có 10 phần tử
13, 22, 30, 14, 21, 5, 21, 12, 15, 19
i = 1
13 22 30 14 21 5 21 12 15 19
13 22 30 14 21 5 12 21 15 19
13 22 30 14 5 21 21 12 15 19
13 22 30 5 14 21 21 12 15 19
13 22 5 30 14 21 21 12 15 19
3
13 5 22 30 14 21 21 12 15 19
5 13 22 30 14 21 21 12 15 19
i = 2
5 12 13 22 30 14 21 21 15 19
i = 3
5 12 13 14 22 30 15 21 21 19
i = 4
5 12 13 14 15 22 30 19 21 21
i = 5
5 12 13 14 15 19 22 30 21 21
i = 6
5 12 13 14 15 19 21 22 30 21
i = 7
5 12 13 14 15 19 21 21 22 30
i = 8
Không thay đổi
5 12 13 14 15 19 21 21 22 30
i = 9
Không thay đổi
5 12 13 14 15 19 21 21 22 30
6.4. S¾p xếp ph©n đo¹n (QuickSort)

1. Chọn một phần tử X(0,i) nào đó làm khoá;
Xếp
- các phần tử nhỏ hơn khoá ở phía trước (so với khoá), được
đoạn B(1);
- các phần tử lớn hơn khoá ở phía sau (so với khoá), được
đoạn B(2);
bằng cách so sánh các phần tử này với chốt và đổi chỗ của chúng
cho nhau hoặc với khoá nếu cần thiết.
Kết quả được dãy < B(1), X(0,i), B(2) >
2. Tiếp tục thực hiện thủ tục trên với hai đoạn B(1) và B(2); Kết
quả được hai dãy con là
< B(1,1), X(1,i), B(1,2) > và < B(2,1), X(2,i), B(2,2) >
Dãy X được xếp lại là
< B(1,1), X(1,i), B(1,2), X(0,i), B(2,1), X(2,i), B(2,2) >
4
Nhận xét:
Nếu mỗi đoạn con trong các đoạn B(1,1), B(1,2), B(2,1), B(2,2)
được sắp thì X là một dãy không giảm.
3. Lặp lại thủ tục trên với các dãy con B(1,1) , B(1,2), B(2,1) và
B(2,2).
Ví dụ:
Xét dãy X= <2, 1, -3, 4, 7,
-6, 5, -8, 9, 8 >
Chỉ số: 1 2 3 4
5 6 7 8 9 10
key = 2
Chọn key X(1) = 2
Chọn hai phần tử cần đổi chỗ
cho nhau
i:=2; j:= 10;

While key > X(i) Do i:=i+1;
Tại chỉ số i: key ≤ X(i); i = 4
While key < X(j) Do j:=j-1;
Tại chỉ số j: key ≥ X(j);
j = 8
2, 1, -3, 4, 7, -6, 5, -8, 9,
8
i j
Đổi chỗ X(i) và X(j) 2, 1, -3, -8, 7, -6, 5, 4, 9,
8
Lặp lại thủ tục trên: tăng i trước,
cố định j sau đó mới tăng j:
i<j
i = 5, j=6
2, 1, -3, -8, 7, -6, 5, 4, 9,
8
i j
Đổi chỗ X(i) và X(j), kết quả: 2, 1, -3, -8, -6, 7, 5, 4,
9, 8
If i=j-1 then
Đổi_chỗ( key,X(i)):
-6, 1, -3, -8, 2, 7, 5, 4, 9,
8
Có 2 đoạn <-6,1,-3, -8>, <2>, <7, 5,4,
9,8>
Lượt thứ 2:
a) Xét đoạn con B(2) := < 7, 5, 4, 9, 8 >
Chọn key X(1) = 7
Chọn hai phần tử cần đổi chỗ
cho nhau

i:=2; j:= 5;
While key > X(i) Do i:=i+1;
Tại chỉ số i: key ≤ X(i); i = 4
5
While key < X(j) Do j:=j-1;
Tại chỉ số j: key ≥ X(j);
i ≥ j
j = 3
7, 5, 4, 9, 8
j i
Do i ≥ j không đổi chỗ X(i) và
X(j) mà đổi chỗ key và X(j):
4, 5, 7, 9, 8
Chi tiết mức 1:
Xem xét đoạn X(l) ... X(r);
+ Nếu l>=r thì ngừng việc xem xét;
+ Nếu l<r thì xem xét tiếp:
1. Chọn key := X(l);
2. Đặt i:=l+1; j:=r;
3. While X(i) > key do i := i+1;
4. While key < X(j) do j := j -1;
5. Nếu i<j thì
+ Đổi_chỗ(X(i) và X(j));
+ Quay lên 3. và tiếp tục;
Ngược lại, nếu i>=j thì kết thúc vòng lặp;
6. Đổi chỗ key = X(l) và X(j)
7. Xem xét đoạn X(l) ... X(j-1);
8. Xem xét đoạn X(j+1) ... X(r);
Chi tiết mức 2:
Procedure SXN(L,R:integer);

If L<R then
Begin
key:=x[L];
i := L+1;
j := R;
While i<=j Do
while x[i]<=key do i:=i+1;
while x[j]>key Do j:=j-1;
If i<j then Doi_cho(x[i],x[j]);
Doi_cho(x[L],x[j]);
SXN(L,j-1);
SXN(j+1,R);
End;
Kí hiệu
- T(k) là số phép toán cần thực hiện để sắp xếp dãy có độ dài k:
X(l..r), r=l+k-1;
- P(k) là số phép toán cần thiết để phân đoạn dãy có độ dài k thành 2
đoạn con;
6