Phân hoạch Hoare — vì sao danh sách đã xếp sẵn lại làm Quicksort chậm nhất?

``` Đưa một danh sách 1 000 tên ĐÃ xếp sẵn cho Quicksort, máy phải so sánh bao nhiêu lần? Nếu chốt luôn là phần tử đầu: hơn 500 000 lần — còn nhiều hơn cả sắp xếp chọn. Video đi lại từ đầu: ý tưởng chia quanh một chốt của Tony Hoare, phân hoạch bằng hai con trỏ, cái bẫy "sợi dây" khi mảng đã sắp, và mẹo rút thăm chốt ngẫu nhiên đưa con số xuống khoảng 12 000. Có chạy tay đầy đủ phân hoạch Hoare trên mảng 5 3 1 9 8 2 4 7 theo đúng dạng bài thi. Video bổ trợ Buổi 4 — Chia để trị của học phần COS157 Phân tích & Thiết kế Giải thuật (HUTECH). Đọc kèm Levitin, Introduction to the Design and Analysis of Algorithms (3rd ed.), §5.2. MỤC LỤC 0:00 Danh sách đã xếp sẵn tốn bao nhiêu phép so sánh? 0:29 Cách ai cũng nghĩ ra: sắp xếp chọn và Mergesort 1:06 Chia quanh một chốt: phân hoạch Hoare 1:46 Cái bẫy: cây đệ quy thành sợi dây 2:12 Mẹo: rút thăm chốt 2:55 Phân hoạch tám số theo dạng bài thi 3:45 Chạy trọn Quicksort, cây đệ quy 4:30 Cân hay lệch: Θ(n log n) và Θ(n²) 5:02 Ngoài đời thực: từ Matxcơva 1959 tới std::sort 5:23 Câu hỏi để mang về Tự thử: mở mô phỏng Quicksort của Buổi 4 (Bu4_quicksort_visualizer.html, trên LMS). Lưu ý: mô phỏng dùng bản Hoare kiểu CLRS — chốt không nhất thiết dừng ở vị trí j như trong video. Câu hỏi treo: nếu cả 1 000 số đều bằng nhau, phân hoạch Hoare chia đều hay lại thành sợi dây? Còn cách dồn số Lomuto học trên lớp thì sao? Nguồn C. A. R. Hoare, "Algorithm 63, Partition; Algorithm 64, Quicksort; Algorithm 65, Find", Communications of the ACM 4(7), 321–322, 1961. C. A. R. Hoare, "Quicksort", The Computer Journal 5(1), 10–16, 1962. D. Musser, "Introspective Sorting and Selection Algorithms", Software: Practice and Experience 27(8), 983–993, 1997. A. Levitin, Introduction to the Design and Analysis of Algorithms, 3rd ed., §5.2. Hình: Manim Community · Giọng đọc: VieNeu-TTS · Biên soạn: Nguyễn Quang Trung, Khoa Công nghệ Thông tin, HUTECH. #COS157 #HUTECH #ThuatToan #Quicksort #ChiaDeTri ```