Slide bài giảng 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

Tóm lược nội dung

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:

Em sẽ chọn làm việc nào trong một trong hai việc sau đây? 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.

NỘI DUNG BÀI HỌC GỒM

• 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 
• Luyện tập
• Vận dụng

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: 

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

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

Nội dung gợi ý:

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

Hãy nêu kết luận về thuật toán sắp xếp nhanh khi áp dụng phương pháp phân đoạn Lomuto.

Nội dung gợi ý:

- 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

+ Nêu ý tưởng chính của thuật toán sắp xếp nhanh áp dụng phân đoạn Hoare ?

+ Hãy trình bày mã giả cho phân đoạn Hoare và mã lệnh Python tương ứng.

Nội dung gợi ý:

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: Viết kết luận sau khi hoàn thành Nhiệm vụ 1,2,3 

Nội dung gợi ý:

- 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: Sau khi kết thúc vòng lặp thứ hai của thuật toán nổi bọt để sắp xếp dãy số sau theo thứ tự tăng dần, thu được dãy số là?

Dãy số ban đầu: 14, 6, 8, 3, 19

A. 14, 6, 8, 19, 3.

B. 3, 14, 6, 8, 19.

C. 3, 6, 19, 14, 8.

D. 3, 6, 14, 8, 19.

Câu 2: Dãy số sau là kết quả khi thực hiện vòng lặp thứ mấy khi sử dụng thuật toán sắp xếp nổi bọt để sắp xếp dãy số 5, 3, 8, 2, 5 theo thứ tự tăng dần?

Kết quả: 2, 5, 3, 8, 5.

A. 1.

B. 2.

C. 3.

D. 4.

Câu 3: Phát biểu nào không đúng khi nói về thuật toán sắp xếp chọn?

A. Thuật toán thực hiện việc chọn số lớn nhất trong dãy chưa được sắp xếp.

B. Đưa số nhỏ nhất chưa được sắp xếp về vị trí đầu tiên của dãy chưa được sắp xếp.

C. Lặp lại quá trình chọn số nhỏ nhất chưa sắp xếp và đưa về vị trí đầu tiên của dãy cho đến khi dãy chỉ còn một phần tử.

D. Thực hiện sắp xếp dãy phần tử không giảm (hoặc không tăng).

Câu 4: Dùng thuật toán sắp xếp chọn để sắp xếp dãy sau tăng dần, sau khi thực hiện bước thứ 2 ta thu được dãy số nào?

Dãy số ban đầu: 19, 16, 8, 25

A. 19, 16, 25, 8.

B. 16, 19, 25, 8.

C. 19, 25, 8, 16.

D. 8, 16, 19, 25.

Câu 5: Chỉ ra phương án sai:

Ý nghĩa của việc chi bài toán thành bài toán nhỏ hơn là:

A. Giúp công việc đơn giản hơn.

B. Giúp công việc dễ giải quyết hơn.

C. Làm cho công việc trở nên phức tạp hơn.

D. Giúp bài toán trở nên dễ hiểu hơn.

Đá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 bước sau:

a) Điều chỉnh thủ tục phân đoạn để tạo hàm quickSort_down sắp xếp theo thứ tự giảm dần. Gợi ý: Thay đổ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 điều chỉnh để có hàm quickSort_tuple_down sắp xếp danh sách các cặp (tên học sinh, điểm môn học) theo điểm môn học giảm dần. Gợi ý: Thay đổi đầu vào thành danh sách các cặp và thực hiện so sánh theo điểm môn học.