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
(cid:1) Chia để trị (cid:1) Phân hoạch (cid:1) Phân tích trường hợp xấu nhất (cid:1) Phân hoạch ngẫu nhiên (cid:1) Phân tích
1
Nội Dung
(cid:1) Đề xuất bởi C.A.R. Hoare, 1962 (cid:1) Dựa trên kỹ thuật Chia – Để – Trị (cid:1) Hiệu quả trong thực tế (tinh chỉnh)
2
Sắp Xếp Nhanh
Chia Để Trị
(cid:1) Chia: phân hoạch mảng thành 2 mảng con dựa trên phần tử chốt (cid:2) sao cho các phần tử thuộc mảng con bên trái ≤ (cid:2) và các phần tử thuộc mảng con bên phải ≥ (cid:2)
(cid:1) Trị: áp dụng đệ quy sắp xếp 2 mảng con (cid:1) Gộp: hiển nhiên
Sắp xếp nhanh mảng (cid:1)-phần tử tăng dần:
3
Lưu ý: phân hoạch với thời gian tuyến tính
⇒ ⇒
(cid:6) (cid:8), (cid:9) chốt (cid:6) (cid:8)
Phân Hoạch – Mã Giả Partition (cid:5)(cid:6), (cid:8), (cid:9)(cid:10)
(cid:2) ← (cid:6) (cid:8) (cid:13) ← (cid:8) for (cid:14) ← (cid:8) (cid:15) 1 to (cid:9) do if (cid:6) (cid:14) ≤ (cid:2) then (cid:13) ← (cid:13) (cid:15) 1 exchange (cid:6) (cid:13) ↔ (cid:6) (cid:14)
exchange (cid:6) (cid:8) ↔ (cid:6) (cid:13) return (cid:13) Duy trì
4
Phân Hoạch – Ví Dụ
5 8 3 2 11 i=1 j j=2->4
6 10 13 i 6 8 i=2
3 2 11 j j=5->6
5 13 10 i 5 6 8 13
3 10 i 3 5 6 8 13 10 11
5
2 i 3 6 5 2 i=3 2 11 j j=7 i=4 j j=8 8 13 10 11 i=4
Phân Hoạch – Cách Khác
Partition (cid:5)(cid:6), (cid:8), (cid:9))
(cid:2) ← (cid:6) (cid:9)
⇒ (cid:6) (cid:8), (cid:9) ⇒ chốt (cid:6) (cid:9)
Xem tr. 171-172
6
7
Phân Hoạch – Bài Tập 7.1-1 tr.173
Sắp Xếp Nhanh - Mã Giả
QuickSort (cid:5)(cid:6), (cid:8), (cid:9)) if (cid:8) < (cid:9) then
(cid:19) ← Partition (cid:6), (cid:8), (cid:9) QuickSort ((cid:6), (cid:8), (cid:19) − 1) QuickSort ((cid:6), (cid:19) + 1, (cid:9))
8
Lời gọi hàm đầu tiên: QuickSort (cid:5)(cid:6), 1, (cid:1))
(cid:1) 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) (cid:1) 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.
(cid:1) Cho (cid:21)(cid:5)(cid:1)(cid:10) là thời gian chạy trong trường
Sắp Xếp Nhanh - Phân Tích
9
hợp xấu nhất với mảng (cid:1) phần tử.
(cid:1) Mảng đã được sắp xếp. (cid:1) Phân hoạch dựa trên phần tử chốt là phần tử
Trường Hợp Xấu Nhất
lớn nhất hoặc nhỏ nhất của mảng.
(cid:1) Một trong hai mảng con luôn luôn không có
phần tử nào.
10
(cid:21) (cid:1) = (cid:21) 0 (cid:15) (cid:21) (cid:1) − 1 + (cid:24) (cid:1) = (cid:24) 1 + (cid:21) (cid:1) − 1 + (cid:24) (cid:1) = (cid:21) (cid:1) − 1 + (cid:24) (cid:1) ∈ (cid:24) (cid:1)(cid:26)
Trường Hợp Xấu Nhất
(cid:1) Thay thế (cid:1) Số học (cid:1) Cây đệ quy (cid:1) Định lý tổng quát
(cid:1)Phải ở dạng (cid:21) (cid:1) = (cid:27)(cid:21) (cid:1)/(cid:29) (cid:15) (cid:30) (cid:1)
11
(cid:21) (cid:1) = (cid:21) (cid:1) − 1 + (cid:24) (cid:1)
Trường Hợp Tốt Nhất !!!
Partition chia mảng thành 2 phần bằng nhau (may mắn)
(cid:21) (cid:1)
(giống MergeSort)
= 2(cid:21) (cid:1)/2 (cid:15) (cid:24) (cid:1) = (cid:24) (cid:1) log (cid:1)
12
Trường Hợp Khác
Partition chia mảng với tỉ lệ
?
:
# #$
& #$
(cid:21) (cid:1)
= (cid:21)
(cid:1) (cid:15) (cid:21)
(cid:1) (cid:15) (cid:24) (cid:1)
# #$
& #$
Thời gian chạy (cid:21) (cid:1) = ?
((cid:1) log#$ (cid:1) ≤ (cid:21) (cid:1) ≤ ((cid:1) log#$/& (cid:1) (cid:15) )(cid:5)(cid:1)(cid:10)
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
tốt nhất xấu nhất
* (cid:1) = 2+ (cid:1)/2 + (cid:24) (cid:1) + (cid:1) = * (cid:1) − 1 + (cid:24) (cid:1)
* (cid:1) = 2 *
− 1 + (cid:24)
+ (cid:24) (cid:1)
(cid:1) 2
(cid:1) 2
= 2*
− 1 + (cid:24) (cid:1)
(cid:1) 2
* (cid:1) ∈ (cid:24) (cid:1) log (cid:1)
14
Phân Hoạch Ngẫu Nhiên
Phân hoạch dựa trên phần tử ngẫu nhiên: (cid:1) Thời gian chạy không phụ thuộc vào dữ
(cid:1) Không cần giả thiết về phân phối của dữ
liệu đầu vào.
(cid:1) Không dữ liệu nào tạo nên trường hợp
liệu đầu vào.
(cid:1) Trường hợp xấu nhất chỉ do hàm sinh số
xấu nhất.
15
ngẫu nhiên.
(cid:1) Giả thiết khi phân tích thời gian chạy (cid:1) Mảng bao gồm các phần tử khác nhau
(cid:1) Mảng có các phần tử giống nhau? (cid:1) Trường hợp đặc biệt, mảng toàn các
Phân Hoạch – Vấn Đề Khác
16
phần tử giống nhau (cid:1) Thời gian chạy theo trường hợp xấu nhất
(cid:1) Giả thiết khi phân tích thời gian chạy (cid:1) Mảng bao gồm các phần tử khác nhau
(cid:1) Mảng có các phần tử giống nhau? (cid:1) Trường hợp đặc biệt, mảng toàn các
Phân Hoạch – Vấn Đề Khác
17
phần tử giống nhau (cid:1) Thời gian chạy theo trường hợp xấu nhất
(cid:1) Phân hoạch thành 3 mảng con
(cid:1) Mảng con bên trái < (cid:2) (cid:1) Mảng con bên phải > (cid:2) (cid:1) Mảng con ở giữa = (cid:2)
(cid:1) Thời gian chạy nhanh hơn (cid:1) Trường hợp đặc biệt, tất cả các phần tử
Phân Hoạch – Vấn Đề Khác
(cid:1) Mã giả?
18
mảng giống nhau (cid:1) Thời gian chạy tuyến tính
(cid:1) Sắp xếp nhanh nói chung là thuật toán
Áp Dụng Thực Tế
(cid:1) Thông thường sắp xếp nhanh chạy
sắp xếp khá tốt.
(cid:1) Sắp xếp nhanh có thể hưởng lợi đáng kể
nhanh hơn gấp đôi so với sắp xếp gộp. (cid:1) Hằng số ( trong (cid:24) (cid:1) tương đối nhỏ
(cid:1) Sắp xếp nhanh chạy khá tốt với cả bộ
từ việc tùy chỉnh mã.
19
nhớ đệm và bộ nhớ ảo.
