Giáo án chuyên đề Khoa học máy tính 11 kết nối Bài 9: Sắp xếp trộn (P1)

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 chia lớp thành các nhóm, yêu cầu thảo luận để hoàn thành Hoạt động 1 SGK trang 40:

Quan sát và thực hiện các bước theo ý tưởng của thuật toán sắp xếp trộn để biết thuật toán này là mô hình kĩ thuật chia để trị.

Em có nhận xét gì về đặc thù của các giai đoạn 1, 2, 3 trong sơ đồ dưới đây?

- GV yêu cầu các nhóm quan sát và thực hiện ý tưởng chính của sắp xếp trộn theo sơ đồ hình 9.1

- GV nêu ý nghĩa của việc trộn: Trộn hai dãy đã sắp xếp thành một dãy lớn hơn cũng sẽ được sắp xếp.

- GV giao cho các nhóm nghiên cứu và mô tả ú tưởng của sắp xếp trộn theo ba bước Chia, Trị và Kết hợp.

- GV kết luận về ý tưởng chia để trị của sắp xếp trộn.

- GV cho HS thảo luận cặp đôi, trả lời Câu hỏi (SGK – tr41) để củng cố kiến thức:

+ Câu 1: Hãy thực hiện thao tác trộn hai dãy sau: B = 1, 4, 7; C = 2, 3, 6.

+ Câu 2: Thực hiện sắp xếp dãy 3, 2, 7, 1, 6, 5 theo các bước tương tự trên.

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

- Các nhóm HS tìm hiểu ý tưởng thuật toán sắp xếp trộn trong SGK.

- HS thảo luận nhóm, hoàn thành bài tập phần Câu hỏi.

- GV theo dõi, hỗ trợ HS trong quá trình học tập.

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

- GV mời đại diện các nhóm trình bày kết quả thảo luận của nhóm mình.

- Đại diện các nhóm xung phong trả lời Câu hỏi (SGK – tr41)

Câu 1: Thực hiện bằng tay trộn hai dãy B = 1, 4, 7 và C = 2, 3, 6.

Mỗi bước sau mô tả một thao tác đơn thực hiện trộn hai dãy B, C, kết quả trả về dãy mới A.

Bước 1. Đưa 1 vào A.

Bước 2. Đưa 2 vào A.

Bước 3. Đưa 3 vào A.

Bước 4. Đưa 4 vào A.

Bước 5. Đưa 6 vào A.

Bước 6. Đưa 7 vào A.

Kết thúc dãy A sẽ là 1, 2, 3, 4, 6, 7.

Câu 2: Thực hiện sắp xếp trộn dãy 3, 2, 7, 1, 6, 5 theo sơ đồ.

- 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, bổ sung, tuyên dương ghi điểm các nhóm làm tốt.

- GV tổng kết lại nội dung.

- GV chuyển sang nội dung tiếp theo.

1. Ý tưởng thuật toán sắp xếp trộn

- Hoạt động 1

Giai đoạn 1. Từ dãy gốc ban đầu chúng ta tách chia đôi làm hai dãy con, mỗi dãy con có kích thước bằng ½ kích thước của dãy gốc. Quá trình này chính là bước Chia của kĩ thuật chia để trị.

Giai đoạn 2. Khi tất cả các dãy con thu được đều chỉ còn một phần tử. Tất cả các dãy này hiển nhiên đều đã được sắp xếp đúng. Đây chính là bước Trị tương ứng của chiến lược chia để trị.

Giai đoạn 3. Từ các dãy đã sắp xếp xong, chúng ta sẽ trộn chúng lại với nhau, mỗi lần trộn hai dãy đã sắp xếp để tạo thành một dãy lớn hơn cũng được sắp xếp đúng. Quá trình trộn sẽ kết thúc khi nhân được đúng một dãy chính là dãy ban đầu nhưng đã sắp xếp xong. Đây chính là quá trình Kết hợp tương ứng của kĩ thuật chia để trị.

*Kết luận

Ý tưởng của thuật toán sắp xếp trộn được thực hiện qua 3 bước: Chia nhỏ dãy gốc thành các dãy với kích thước nhỏ hơn (bằng ½ dãy ban đầu), tiếp tục cho đến khi nhận được các dãy con đã sắp xếp đúng thì tiến hành trộn các dãy này để nhận được kết quả cuối cùng. Các bước trên chính là kĩ thuật chia để trị.

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 chia lớp thành các nhóm, yêu cầu thảo luận để hoàn thành Hoạt động 2 SGK trang 41:

Cùng thực hiện các bước cụ thể triển khai ý tưởng và cài đặt chương trình cho thuật toán sắp xếp trộn.

- GV yêu cầu các nhóm thảo luận về các bước chính của sắp xếp trộn.

- GV chốt lại: Có thể hiểu sắp xếp trộn luôn bao gồm hai quá trình:

(1) Tách dãy gốc thành hai dãy con với mỗi dãy con có kích thước ½ dãy ban đầu. Dùng đệ quy để sắp xếp hai dãy con này.

(2) Sau đó, dùng thuật toán trộn để trộn hai dãy con đã sắp xếp thành dãy ban đầu nhưng đã được sắp xếp.

Thuật toán sắp xếp trộn được mô tả tổng quát như sau:

Trong đó lệnh 6 chính là thuật toán "trộn" đóng vai trò rất quan trọng của sắp xếp trộn.

- GV phân tích để HS hiểu được bản chất và ý nghĩa của sắp xếp trộn.

- GV cho HS thảo luận cặp đôi, trả lời Câu hỏi (SGK – tr43) để củng cố kiến thức:

+ Câu 1: Trong chương trình 1 (trộn hai dãy B, C), vòng lặp tại dòng 6 có nhiều nhất là bao nhiêu bước lặp?

+ Câu 2: Mô tả các bước thực hiện chương trình 2 nếu dãy gốc A chỉ có một phần tử.

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

- Các nhóm HS tìm hiểu các bước thực hiện sắp xếp trộn trong SGK.

- HS thảo luận nhóm, hoàn thành bài tập phần Câu hỏi.

- GV theo dõi, hỗ trợ HS trong quá trình học tập.

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

- GV mời đại diện các nhóm trình bày kết quả thảo luận của nhóm mình.

- Đại diện các nhóm xung phong trả lời Câu hỏi (SGK – tr43)

Câu 1: Vòng lặp 6 có nhiều nhất là m + n bước lặp.

Câu 2: Nếu dãy gốc có 1 phần tử thì thuật toán sắp xếp trộn sẽ không thực hiện gì và trả về ngay dãy gốc.

- 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, bổ sung, tuyên dương ghi điểm các nhóm làm tốt.

- GV tổng kết lại nội dung.

- GV chuyển sang nội dung tiếp theo.

2. Mô tả thuật toán sắp xếp trộn

- Hoạt động 2

a) Thuật toán trộn hai dãy (merge algorithm)

- Giả sử cho trước hai dãy đã được sắp thứ tự B và C có số phần tử lần lượt là m, n. Thuật toán merge(B, C) sẽ được thực hiện "trộn" hai dãy trên và đưa kết quả vào dãy A. Quy trình trộn này rất tự nhiên và được minh họa trong sơ đồ hình 9.2

Thuật toán 1. Thuật toán trộn hai dãy

b) Thuật toán sắp xếp trộn (mergeSort)

- Thuật toán sắp xếp trộn được mô tả bởi hàm mergeSort(A) trong chương trình sau.

Thuật toán 2. Thuật toán sắp xếp trộn

- Đoạn chương trình sau sẽ thực hiện sắp xếp dãy A và đưa kết quả đã sắp xếp vào dãy B. Lời gọi hàm đệ quy là:

1 A = [2, 1, 10, 0, -7, -20, 19, 100, -3, -2, 9, 11]

2 B = mergeSort(A)

*Kết luận

- Thuật toán sắp xếp trộn sẽ bao gồm một hàm mergeSort(), hàm này sẽ tiến hành các bước chính của thuật toán và gọi hàm trộn hai dãy đã sắp xếp merge() khi thực hiện bước kết hợp.