Bài giảng "Thiết kế và đánh giá thuật toán: Sắp xếp nhanh" cung cấp cho người học các kiến thức: 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. . | 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 . 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 , , ⇒ ⇒ ← ← for ← 1 to do if ≤ then ← 1 exchange ↔ exchange ↔ return , chốt Duy .
