Soạn giáo án điện tử Khoa học máy tính 11 Cánh diều Chủ đề F(CS) Bài 9: Lập trình thuật toán sắp xếp nhanh

Nội dung giáo án

VUI MỪNG CHÀO ĐÓN CÁC EM ĐẾN VỚI BUỔI HỌC HÔM NAY!

KHỞI ĐỘNG

Nếu cần chọn một trong hai việc sau đây, em sẽ chọn làm việc nào? Vì sao?

Từ mô tả thuật toán bằng liệt kê các bước, viết chương trình Python thực hiện thuật toán.

Từ chương trình Python thực hiện thuật toán, viết lại ngắn gọn ý tưởng chính của thuật toán.

BÀI 9: LẬP TRÌNH THUẬT TOÁN SẮP XẾP NHANH

NỘI DUNG BÀI HỌC

Lược đồ phân đoạn trong sắp xếp nhanh

Thuật toán sắp xếp nhanh áp dụng phân đoạn Lomuto

Thuật toán sắp xếp nhanh áp dụng phân đoạn Hoare

Thực hành

1. LƯỢC ĐỒ PHÂN ĐOẠN TRONG SẮP XẾP NHANH

Thảo luận cặp đôi

Đọc hiểu mục 1, quan sát Hình 1 tr.127 SGK và thực hiện các nhiệm vụ sau:

Trình bày về thuật toán sắp xếp nhanh (Quick Sort).

Quan sát Hình 1, hãy mô tả lược đồ phân đoạn dãy số.

Thuật toán sắp xếp nhanh (Quick Sort)

Thuật toán theo chiến lược chia để trị, lặp lại nhiều lần việc phân đoạn dãy đầu vào thành hai đoạn con.

Lược đồ phân đoạn dãy số

Lấy giá trị của một phần tử trong dãy làm pivot (giá trị chốt). Giá trị pivot có thể là bất cứ phần tử nào trong dãy.

Kết quả phân đoạn:

Đoạn con ở nửa dãy bên trái chỉ gồm các phần tử nhỏ hơn hay bằng pivot.

Đoạn con ở nửa dãy bên phải chỉ gồm các phần tử lớn hơn hay bằng pivot.

Phần tử làm pivot được chuyển đến vị trí phân tách hai đoạn.

Hàm thực hiện phân đoạn cần trả về vị trí phân tách dãy thành hai đoạn con vì sau đó sẽ sắp xếp chỉ trong nội bộ hai đoạn con.