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

Thiết Kế & Đánh Giá Thuật Toán<br /> Sắp Xếp Nhanh<br /> TS. Lê Nguyên Khôi<br /> Trường Đại Học Công Nghệ - ĐHQGHN<br /> <br /> Nội Dung<br /> Chia để trị<br />
Phân hoạch<br />
Phân tích trường hợp xấu nhất<br />
Phân hoạch ngẫu nhiên<br />
Phân tích<br />
<br /> <br /> 1<br /> <br /> Sắp Xếp Nhanh<br /> xuất bởi C.A.R. Hoare, 1962<br />
Dựa trên kỹ thuật Chia – Để – Trị<br />
Hiệu quả trong thực tế (tinh chỉnh)<br />
Đề<br /> <br /> 2<br /> <br /> Chia Để Trị<br /> Sắp xếp nhanh mảng
-phần tử tăng dần:<br />
<br /> <br />
<br />
<br /> <br /> Chia: phân hoạch mảng thành 2 mảng con dựa<br /> trên phần tử chốt  sao cho các phần tử thuộc<br /> mảng con bên trái ≤  và các phần tử thuộc<br /> mảng con bên phải ≥ <br /> Trị: áp dụng đệ quy sắp xếp 2 mảng con<br /> Gộp: hiển nhiên<br /> <br /> Lưu ý: phân hoạch với thời gian tuyến tính<br /> 3<br /> <br /> Phân Hoạch – Mã Giả<br /> Partition , , <br /> <br /> ⇒<br /> ⇒<br /> ←<br /> ←<br /> for  ←   1 to do<br /> if   ≤  then<br /> ←<br /> 1<br /> exchange  <br /> ↔  <br /> exchange   ↔  <br /> return <br /> <br />  , <br /> chốt  <br /> <br /> Duy trì<br /> 4<br /> <br />