Giáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 5: 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