Bài giảng Thiết Kế & Đánh Giá Thuật Toán - Sắp xếp nhanh - Lê Nguyên Khôi

Nội dung text: Bài giảng Thiết Kế & Đánh Giá Thuật Toán - Sắp xếp nhanh - Lê Nguyên Khôi

1. ế ế ậ ắ ế a ườ ạ ọ ệ
2. ộ
   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
3. ắ ế a
   Đề 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
4. aể ị 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
5. ạ ả Partition ch ốt for to do if ≤ then exchange exchange return Duy trì 4
6. ạ ụ 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
7. ạ Partition , , ) ⇒ , ← ⇒ ch ốt Xem tr. 171-172 6
8. ạ ậ 7
9. ắ ế a ả QuickSort , , ) if < then ← Partition , , QuickSort (, , − 1) QuickSort (, + 1, ) Lời gọi hàm đầ u tiên : QuickSort , 1, ) 8
10. ắ ế a
    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
11. ườ ợ ấ ấ
    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
12. ườ ợ ấ ấ = − 1 +
    Thay th ế
    Số học
    Cây đệ quy
    Đị nh lý tổng quát
    Ph ải ở dạng = / 11
13. ườ ợ ố ấ Partition chia mảng thành 2 ph ần bằng nhau (may mắn) = 2 /2 = log (gi ống MergeSort ) 12
14. ườ ợ Partition chia mảng với tỉ lệ : ? = Th ời gian ch ạy =? log ≤ ≤ log / 13
15. ườ ợ 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 = − 1 + xấu nh ất = − 1 + + = − 1 + ∈ log 14
16. ạ ẫ 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
17. ạ ấ ề
    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
18. ạ ấ ề
    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
19. ạ ấ ề
    Phân ho ạch thành 3 mảng con
    Mảng con bên trá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
20. ụ ự ế
    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