Bài giảng Thiết kế và đánh giá thuật toán - Sắp xếp nhanh - Lê Nguyên Khôi

Thiết Kế & Đánh Giá Thuật Toán
Sắp Xếp Nhanh
TS. Lê Nguyên Khôi
Trường Đại Học Công Nghệ - ĐHQGHN
Nội Dung

 Chia để trị

 Phân hoạch

 Phân tích trường hợp xấu nhất

 Phân hoạch ngẫu nhiên

 Phân tích
1
Sắp Xếp Nhanh

Đề xuất bởi C.A.R. Hoare, 1962

Dựa trên kỹ thuật Chia – Để – Trị

Hiệu quả trong thực tế (tinh chỉnh)
2
Chia Để Trị
Sắp xếp nhanh mảng 
-phần tử tăng dần:

 Chia: phân hoạch mảng thành 2 mảng con dựa
trên phần tử chốt  sao cho các phần tử thuộc
mảng con bên trái ≤  và các phần tử thuộc
mảng con bên phải ≥ 

 Trị: áp dụng đệ quy sắp xếp 2 mảng con

 Gộp: hiển nhiên
Lưu ý: phân hoạch với thời gian tuyến tính
3
Phân Hoạch – Mã Giả
Partition , , 	
 ⇒  , 	
 ←   ⇒ chốt  

 ← 
for  ←   1 to 	 do
if   ≤  then

 ← 
  1
exchange  
 ↔  
exchange   ↔  

return 

Duy trì
4
Phân Hoạch – Ví Dụ
6 10 13 5 8 3 2 11 i=1
i j j=2->4
6 5 13 10 8 3 2 11 i=2
i j j=5->6
6 5 3 10 8 13 2 11 i=3
i j j=7
6 5 3 2 8 13 10 11 i=4
i j j=8
2 5 3 6 8 13 10 11 i=4
5
Phân Hoạch – Cách Khác
Partition , , 	) ⇒  , 	
 ←  	 ⇒ chốt  	
Xem tr. 171-172
6
Phân Hoạch – Bài Tập 7.1-1 tr.173
7
Sắp Xếp Nhanh - Mã Giả
QuickSort , , 	)
if  < 	 then
 ← Partition , , 	
QuickSort (, ,  − 1)
QuickSort (,  + 1, 	)
Lời gọi hàm đầu tiên: QuickSort , 1, 
)
8
Sắp Xếp Nhanh - Phân Tích

 Giả sử các phần tử của dãy khác nhau
(không có 2 phần tử nào bằng nhau)

 Thực tế có một số thuật toán phân hoạch
khác tốt hơn cho trường hợp có phần tử
bằng nhau.

 Cho 

 là thời gian chạy trong trường
hợp xấu nhất với mảng 
 phần tử.
9
Trường Hợp Xấu Nhất

 Mảng đã được sắp xếp.

 Phân hoạch dựa trên phần tử chốt là phần tử
lớn nhất hoặc nhỏ nhất của mảng.

 Một trong hai mảng con luôn luôn không có
phần tử nào.
 
 =  0   
 − 1 +  

=  1 +  
 − 1 +  

=  
 − 1 +  

∈  

10
Trường Hợp Xấu Nhất
 
 =  
 − 1 +  


Thay thế

Số học

Cây đệ quy

Định lý tổng quát

Phải ở dạng  
 =  
/   

11
Trường Hợp Tốt Nhất !!!
Partition chia mảng thành 2 phần
bằng nhau (may mắn)
 
 = 2 
/2   

=  
 log 
 (giống MergeSort)
12
Trường Hợp Khác
Partition chia mảng với tỉ lệ #
#$
:
&
#$
?
 
 = 
#
#$

  
&
#$

   

Thời gian chạy  
 =	?
(
 log#$ 
 ≤  
 ≤ (
 log#$/& 
  )

13
Trường Hợp Khác
Giả sử phân hoạch liên tục theo trường hợp
xấu nhất và tốt nhất
* 
 = 2+ 
/2 +  
 tốt nhất
+ 
 = * 
 − 1 +  
 xấu nhất
* 
 = 2 *


2
− 1 + 


2
+  

= 2*


2
− 1 +  

* 
 ∈  
 log 

14
Phân Hoạch Ngẫu Nhiên
Phân hoạch dựa trên phần tử ngẫu nhiên:

 Thời gian chạy không phụ thuộc vào dữ
liệu đầu vào.

 Không cần giả thiết về phân phối của dữ
liệu đầu vào.

 Không dữ liệu nào tạo nên trường hợp
xấu nhất.

 Trường hợp xấu nhất chỉ do hàm sinh số
ngẫu nhiên.
15
Phân Hoạch – Vấn Đề Khác

 Giả thiết khi phân tích thời gian chạy

Mảng bao gồm các phần tử khác nhau

 Mảng có các phần tử giống nhau?

 Trường hợp đặc biệt, mảng toàn các
phần tử giống nhau

 Thời gian chạy theo trường hợp xấu nhất
16
Phân Hoạch – Vấn Đề Khác

 Giả thiết khi phân tích thời gian chạy

Mảng bao gồm các phần tử khác nhau

 Mảng có các phần tử giống nhau?

 Trường hợp đặc biệt, mảng toàn các
phần tử giống nhau

 Thời gian chạy theo trường hợp xấu nhất
17
Phân Hoạch – Vấn Đề Khác

 Phân hoạch thành 3 mảng con

Mảng con bên trái < 

Mảng con bên phải > 

Mảng con ở giữa = 

 Thời gian chạy nhanh hơn

 Trường hợp đặc biệt, tất cả các phần tử
mảng giống nhau

 Thời gian chạy tuyến tính

 Mã giả?
18
Áp Dụng Thực Tế

 Sắp xếp nhanh nói chung là thuật toán
sắp xếp khá tốt.

 Thông thường sắp xếp nhanh chạy
nhanh hơn gấp đôi so với sắp xếp gộp.

 Hằng số ( trong  
 tương đối nhỏ

 Sắp xếp nhanh có thể hưởng lợi đáng kể
từ việc tùy chỉnh mã.

 Sắp xếp nhanh chạy khá tốt với cả bộ
nhớ đệm và bộ nhớ ảo.
19