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

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV nêu một số bài toán sắp xếp, hướng dẫn HS phát biểu rõ ràng từng bài toán với tiêu chí sắp xếp cụ thể:

+ Cho các dãy số, yêu cầu sắp xếp “theo thứ tự tăng dần (giảm dần)”.

+ Cho dãy các xâu kí tự, yêu cầu sắp xếp “theo thứ tự bảng chữ cái”, “theo độ dài tăng dần”,...

+ Sắp xếp các hàng trong một bảng gồm nhiều cột (hay bản ghi trong bảng CSDL) theo một cột nào đó. Ví dụ, có bảng kết quả học tập gồm các cột Họ và tên, Điểm Toán, Điểm Ngữ Văn, Điểm Tin học,... yêu cầu sắp xếp theo điểm môn Tin học giảm dần. Các hàng có trong bảng có dạng như sau:

- GV yêu cầu HS dựa vào các ví dụ trên, kết hợp với đọc hiểu mục 1 tr.122 - 123 SGK trả lời các câu hỏi sau:

1. Sắp xếp có nghĩa là gì?

2. Phân biệt sắp xếp tại chỗ và không tại chỗ.

3. Nghịch thế là gì? Nghịch thế có vai trò gì trong thuật toán sắp xếp.

Bước 2: HS thực hiện nhiệm vụ học tập

- HS đọc và tìm hiểu thông tin mục 1 SGK trang 122, thực hiện nhiệm vụ được giao.

- GV hướng dẫn, theo dõi, hỗ trợ HS khi cần.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV mời 1 - 2 HS trả lời câu hỏi.

- HS khác nhận xét, bổ sung.

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- GV nhận xét câu trả lời của HS, kết luận, chốt kiến thức và yêu cầu HS ghi chép đầy đủ vào vở.

- GV chú ý và dẫn dắt HS sang hoạt động tiếp theo: cặp phần tử là nghịch thế không nhất thiết phải liền kề nhau. Tổng số nghịch thế trong một dãy sẽ lớn hơn số các nghịch thế là cặp phần tử liền kề. Nhưng mỗi khi đổi chỗ một cặp phần tử liền kề thì số nghịch thế chắc chắn sẽ giảm đi, ít nhất là 1. Đây là cơ sở cho ý tưởng thuật toán sắp xếp nổi bọt.

1. Bài toán sắp xếp

- Trong tin học, thuật ngữ sắp xếp đề cấp đến việc tổ chức lại một tập hợp dữ liệu theo một tiêu chí sắp xếp, tức là đáp ứng một yêu cầu cụ thể về trình tự.

- Yêu cầu sắp xếp cần chỉ rõ cách so sánh hai mục dữ liệu để quyết định thứ tự.

Ví dụ: Bài toán sắp xếp đơn giản và minh họa bằng sắp xếp dãy số.

- Đầu vào: Dãy n số a₀, a₁ ,..., a_{n – 1}.

- Đầu ra: Dãy được sắp xếp theo thứ tự tăng dần (không giảm).

Sắp xếp tại chỗ và không tại chỗ

- Một thuật toán không dùng thêm một dãy khác ở bên ngoài dãy ban đầu để thực hiện sắp xếp được gọi là sắp xếp tại chỗ.

- Nếu thuật toán sử dụng một dãy khác ở bên ngoài dãy ban đầu để chứa kết quả thì gọi là sắp xếp không tại chỗ.

Nghịch thế

- Nếu i < j mà a_i > a_j thì cặp hai phần tử (a_i, a_j) gọi là một nghịch thế.

- Một thuật toán sắp xếp dựa trên ý tưởng giảm dần và tiến đến triệt tiêu các nghịch thế trong dãy.

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV yêu cầu HS hoạt động nhóm 3 - 4 HS, trả lời câu hỏi Hoạt động tr.123 SGK:

Dựa trên minh họa diễn biến từng bước của thuật toán sắp xếp nổi bọt được trình bày như ở Hình 1, em hãy nêu tóm tắt ý tưởng của thuật toán này.

- GV yêu cầu nhóm HS đọc hiểu mục 2, quan sát Hình 1, 2 tr.123 - 124 và viết chương trình thuật toán thuật toán sắp xếp nổi bọt.

Bước 2: HS thực hiện nhiệm vụ học tập

- HS đọc hiểu thông tin mục 2, quan sát Hình 1 tr.123 - 124 SGK, thực hiện nhiệm vụ được giao.

- GV theo dõi, hỗ trợ HS trong quá trình học tập, gợi ý HS đọc kĩ Nhận xét tr.124 để cải tiến thêm, giảm bớt một số thao tác thừa, đồng thời cũng thấy được rằng: Nhiều nhất là sau n – 1 lần rà soát dãy thì sẽ sắp xếp xong. Do đó, để kiểm soát điều kiện “không còn xảy ra đổi chỗ”, ở vòng lặp ngoài có thể dùng for hay while đều được.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV mời 1 - 2 nhóm HS trả lời câu hỏi Hoạt động tr.123 SGK:

Ý tưởng của thuật toán sắp xếp nổi bọt: Thực hiện việc sắp xếp giảm dần và tiến đến triệt tiêu hết các nghịch thế trong dãy cho đến khi không còn nghịch thế nào.

- GV mời một số HS thực hiện viết chương trình thuật toán sắp xếp nổi bọt trước lớp và chạy thử kết quả.

- Các HS còn lại nhận xét, bổ sung (nếu có).

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- GV nhận xét kết quả trả lời của HS.

- GV tổng quát kiến thức và yêu cầu HS ghi chép đầy đủ vào vở.

2. Thuật toán sắp xếp nổi bọt (Bubble Sort)

- Ý tưởng sắp xếp nổi bọt (Bubble Sort):

+ Xét lần lượt các cặp phần tử liên tiếp: nếu a_i > a_i+1 thì đổi chỗ [a_i, a_i+1].

+ Lặp lại cho đến khi triệt tiêu hết các cặp nghịch thế.

+ Có thể chứng minh sau vòng lặp 1 thì số lớn nhất trong dãy sẽ được chuyển đến vị trí cuối dãy, tức là phần tử a[n – 1] đã ở đúng vị trí. Như vậy vòng lặp 2 chỉ cần rà soát nghịch thế và đổi chỗ đến vị trí n – 2.

- Sau vòng lặp i thì phần tử a[n – i – 1] đã ở đúng vị trí.

- Mã giả của thuật toán sắp xếp nổi bọt:

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV tổ chức cho nhóm HS tiếp tục hoạt động.

- GV yêu cầu nhóm HS đọc hiểu mục 3, quan sát Hình 3, 4 tr.124 - 125 SGK để hình thành kiến thức mới về thuật toán sắp xếp chèn tuyến tính (Insertion Sort), sau đó thảo luận nhóm viết chương trình Python.

- GV phân tích việc “chèn a_i vào đúng chỗ của nó” trong dãy {a₀, a₁ ,..., a_{i – 1}} thành hai bước:

a) Tìm vị trí đúng của a_i.

b) Dịch cả đoạn {a₀, a₁ ,..., a_{i – 1}} là để làm rõ ý nghĩa của tên gọi “chèn tuyến tính” (Dành cho HS có năng lực, GV có thể ra bài tập, bài thực hành viết chương trình thuật toán sắp xếp chèn nhị phân).

Bước 2: HS thực hiện nhiệm vụ học tập

- Nhóm HS đọc hiểu mục 3, quan sát Hình 3, 4 tr.124 - 125 SGK và thực hiện nhiệm vụ.

- GV hướng dẫn, theo dõi, hỗ trợ HS khi cần.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV mời một số HS thực hiện viết chương trình sắp xếp chèn tuyến tính trước lớp và chạy thử.

- GV mời HS nhóm khác nhận xét, bổ sung.

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- GV nhận xét kết quả thảo luận của HS, thái độ làm việc của HS trong nhóm.

- GV kết luận và yêu cầu HS ghi chép đầy đủ vào vở.

3. Thuật toán sắp xếp chèn tuyến tính (Insertion Sort)

Ý tưởng sắp xếp chèn tuyến tính:

- Vì dãy con a₀ chỉ có một phần tử, nên dãy con này có thứ tự.

- Lặp lại việc chèn a_i  với 1 ≤ i < n như sau:

Xét dãy con a₀,..., a_{i – 1} đã có thứ tự, ta chèn a_i vào dãy con này sao cho dãy con sau khi chèn sẽ có thứ tự.

Mô tả thuật toán chèn tuyến tính:

Mô tả các bước của thuật toán như sau:

Bước 0. i ← 1;

Bước 1.

      if i ≥ n: kết thúc;

     else: val ← a_i; k ← i – 1;

Bước 2.

     if k ≥ 0:

           if a_k > val: a_{k + 1} ← a_k; k ← k – 1; đến Bước 2;

Bước 3. a_{k + 1} ← val; i ← i + 1; đến Bước 1;

Để “chèn a_i vào đúng chỗ của nó” trong dãy a₀, a₁ ,..., a_{i – 1} cần:

a) Tìm được chỗ đúng thứ tự của a_i : Cho k đi từ i – 1 qua trái cho đến khi a_k ≤ a_i hoặc k = – 1.

b) Lấy a_i  ra khỏi dãy; dịch chuyển dãy a_{k + 1} ,..., a_{i – 1} sang phải một vị trí để có chỗ trống tại a_{k + 1}; đưa a_i vào chỗ trống đó.

Mã giả thuật toán sắp xếp chèn tuyến tính

Thuật toán sắp xếp chèn tuyến tính kết hợp làm đồng thời hai việc a) và b) theo cách dịch chuyển dần từng bước sang trái, từ vị trí i tới vị trí k + 1.

- Vòng lặp for bên ngoài kiểm soát việc thực hiện đúng n – 1 bước.

- Vòng lặp while lồng bên trong thực hiện đồng thời cùng lúc hai việc a) và b) trong mỗi bước.

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV nêu các nhiệm vụ, yêu cầu HS hoạt động nhóm (3 - 4 HS) thực hiện nhiệm vụ:

Nhiệm vụ 1. Em hãy thực hiện các công việc sau:

a) Tính số lần lặp của vòng lặp bên trong của thuật toán sắp xếp chèn tuyến tính.

b) Tính số lần lặp của vòng lặp ngoài của thuật toán sắp xếp chèn tuyến tính.

c) Ước lượng độ phức tạp thời gian của thuật toán sắp xếp chèn tuyến tính.

Nhiệm vụ 2. Em hãy viết chương trình Python thực hiện thuật toán sắp xếp nổi bọt.

Nhiệm vụ 3. Em hãy viết chương trình Python thực hiện thuật toán sắp xếp chèn tuyến tính dựa trên mã giả đã cho trong bài học.

Bước 2: HS thực hiện nhiệm vụ học tập

- HS dựa vào kiến thức đã học, thực hành nhiệm vụ được giao.

- GV hướng dẫn, theo dõi, hỗ trợ HS khi cần.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- Các nhóm báo cáo sản phẩm thực hành.

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- GV nhận xét sản phẩm của các nhóm, gợi ý chỉnh sửa nếu chương trình không chạy.

- GV kết luận và chuẩn kiến thức.

4. Thực hành

Nhiệm vụ 1.

a) Số lần lặp của vòng lặp bên trong với bước i sẽ không quá i.

b) Vòng lặp ngoài của thuật toán được thực hiện đúng n – 1 lần như đã nhận xét trong bài học.

c) Ước lượng độ phức tạp thời gian của thuật toán sắp xếp chèn tuyến tính là O(n²) vì không vượt quá tổng 1 + 2 + … + n – 1.

Nhiệm vụ 2 và Nhiệm vụ 3

Kết quả đính kèm dưới Hoạt động 4.

⇨ Kết luận:

- Thuật toán sắp xếp nổi bọt có hai vòng lặp lồng nhau; vòng lặp trong thực hiện đổi chỗ một lượt các cặp phần tử là nghịch thế, vòng lặp ngoài kiểm tra điều kiện “không xảy ra đổi chỗ”.

- Việc tìm vị trí chèn đúng chỗ trong thuật toán sắp xếp chèn có thể thực hiện bằng cách dịch dần từng bước.