Bài giảng Thiết kế và đánh giá thuật toán: Sắp xếp nhanh - TS. Lê Nguyên Khôi

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. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Thiết kế và đánh giá thuật toán: Sắp xếp nhanh - TS. Lê Nguyên KhôiThiết Kế & Đánh Giá Thuật ToánSắp Xếp NhanhTS. Lê Nguyên KhôiTrường Đại Học Công Nghệ - ĐHQGHNNội DungChia để 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ích1Sắp Xếp Nhanhxuấ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) Đề2Chia Để 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ựatrên phần tử chốt sao cho các phần tử thuộcmảng con bên trái ≤ và các phần tử thuộcmảng con bên phải ≥ Trị: áp dụng đệ quy sắp xếp 2 mảng conGộp: hiển nhiênLưu ý: phân hoạch với thời gian tuyến tính3Phân Hoạch – Mã GiảPartition , , ⇒⇒←←for ← 1 to doif ≤ then ←1exchange ↔ exchange ↔ return , chốt Duy trì4