Giáo án và PPT Khoa học máy tính 11 cánh diều Bài 9: Lập trình thuật toán sắp xếp nhanh

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

HOẠT ĐỘNG KHỞI ĐỘNG

GV đặt vấn đề, yêu cầu HS trả lời câu hỏi Khởi động tr.127 SGK:

          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?

1) 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.

2) 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.

HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC

Hoạt động 1: Lược đồ phân đoạn trong sắp xếp nhanh

GV yêu cầu học sinh trao đổi: 

+ 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ố.

Sản phẩm dự kiến:

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ình 1. Kết quả phân đoạn: đoạn trái = {i|lo ≤ i ≤ p – 1}, đoạn phải = {j|p + 1 ≤ i ≤ hi}

- 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.

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

Nêu kết luận về Thuật toán sắp xếp nhanh áp dụng phân đoạn Lomuto

Sản phẩm dự kiến:

- Mã giả của thuật toán Lomuto phân đoạn dãy số a, trong đó:

lo là chỉ số đầu mút trái

hi là chỉ số đầu mút phải

- Ý tưởng của thuật toán Lomuto: Chọn pivot là giá trị phần tử đứng cuối dãy số. 

+ Duy trì chỉ số i ở vị trí phân tách;

+ Duyệt dãy số bằng một chỉ số j khác và đảo giá trị các phần tử sao cho các phần tử từ vị trí i – 1 về đầu mút trái nhỏ hơn hay bằng pivot; các phần tử từ vị trí i + 1 đến j lớn hơn pivot, riêng phần tử ở vị trí i đúng bằng pivot.

- Mã lệnh Python thực hiện sắp xếp nhanh bằng phân đoạn Lomuto:

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

+ Ý tưởng chính của thuật toán sắp xếp nhanh áp dụng phân đoạn Hoare là gì?

+ Trình bày mã giả thực hiện phân đoạn Hoare và mã lệnh Python tương ứng

Sản phẩm dự kiến:

Lược đồ phân đoạn Hoare

- Ý tưởng của thuật toán: 

+ Đổi chỗ nhảy qua điểm phân tách (pivot), rà soát từ hai phía, trái và phải, cùng tiến dần từng bước vào giữa.

+ Tạm dừng khi phát hiện phần tử vi phạm yêu cầu phân đoạn ở mỗi phía và đổi chỗ chúng cho nhau.

+ Rà soát từ hai điểm tạm dừng đi vào giữa cho đến khi gặp nhau thì kết thúc việc phân đoạn.

+ Điểm gặp nhau là vị trí phân tách dãy thành hai đoạn con.

- Mã giả của thuật toán sắp xếp nanh áp dụng phân đoạn Hoare:

- Mã lệnh Python của thuật toán phân đoạn dãy số a, xuất phát với pivot là đầu dãy.

Hoạt động 4: Thực hành 

HS thảo luận trả lời câu hỏi: Nêu kết luận sau khi hoàn thành Nhiệm vụ 1,2,3

Sản phẩm dự kiến:

- Thuật toán sắp xếp nhanh có thể áp dụng một trong hai lược đồ phân đoạn: theo Lomuto hoặc theo Hoare.

- Lược đồ Lomuto thực hiện phân đoạn bằng cách kiểm tra theo một chiều từ trái sang phải đổi chỗ và dịch chuyển dần vị trí phân tách hai dãy con cho đến khi thỏa mãn yêu cầu phân đoạn.

- Lược đồ Hoare thực hiện phân đoạn bằng cách kiểm tra theo hai chiều, từ hai đầu dây số tiến dần vào giữa, đổi chỗ để thoả mãn yêu cầu phân đoạn; kết thúc khi gặp nhau.

HOẠT ĐỘNG LUYỆN TẬP

Câu 1. Điểm phân tách được gọi là

A. pivot.               B. hivot.                         C. mivot.                        D. divot.

Câu 2. Có bao nhiêu lược đồ phân đoạn có thể áp dụng trong thuật toán sắp xếp nhanh?

A. 5.                     B. 4.                               C. 3.                               D. 2.

Câu 3. Trong lược đồ phân đoạn dãy số, giá trị pivot có thể lấy phần tử nào trong dãy?

A. Phần tử ở đầu dãy.                                  B. Phần tử ở cuối dãy.

C. Phần tử ở giữa dãy.                                 D. Bất kì phần tử nào trong dãy.

Câu 4. Lược đồ Lomuto thực hiện phân đoạn bằng cách kiểm tra dãy số theo chiều nào?

A. Từ phải sang trái.                                    B. Từ trái sang phải.

C. Theo hai chiều tiến vào giữa.                   D. Từ giữa ra hai bên.

Câu 5. Độ phức tạp của thuật toán Quick Sort trong trường hợp xấu nhất đó là

A. O(n).                B. O(log₂n).                    C. O(n²).               D. O(Cⁿ).

Đáp án gợi ý:

HOẠT ĐỘNG VẬN DỤNG

GV yêu cầu HS hoạt động nhóm đôi hoàn thành Vận dụng SGK trang 130: Em hãy thực hiện các công việc sau:

a) Sửa lại thủ tục phân đoạn để có hàm quickSort_down sắp xếp theo thứ tự giảm dần.

Gợi ý: Sửa đổi phép so sánh trong câu lệnh if a[j] <= pivot:thành if a[j] >= pivot:

b) Tiếp tục sửa lại để có hàm quickSort_tuple_down sắp xếp danh sách các cặp, ví dụ (tên học sinh, điểm môn học) theo điểm môn học giảm dần.

Gợi ý: Sửa đổi đầu vào thành danh sách các cặp (tên học sinh, điểm môn học) và thực hiện so sánh theo điểm môn học.