Tin học 11 Bài 21: Các thuật toán sắp xếp đơn giản Giải Tin học 11 Định hướng Khoa học máy tính Kết nối tri thức

Bài trước

Mục lục

Bài sau

Giải bài tập SGK Tin học 11 trang 99→103 sách Kết nối tri thức với cuộc sống giúp các em học sinh lớp 11 xem gợi ý giải các câu hỏi Bài 21: Các thuật toán sắp xếp đơn giản thuộc Chủ đề 6: Kỹ thuật lập trình.

Soạn Tin học 11 Kết nối tri thức Bài 21 giúp các bạn học sinh nắm được kiến thức về thuật toán sắp xếp chèn, thuật toán sắp xếp chọn, thuật toán sắp xếp nổi bọt. Đồng thời qua tài liệu này giúp giáo viên nhanh chóng xây dựng hoàn thiện giáo án dạy học của mình.

Tin học 11 Bài 21: Các thuật toán sắp xếp đơn giản

Nội dung bài học Tin 11 Bài 21

1. Thuật toán sắp xếp chèn

Hoạt động 1: Quan sát sơ đồ mô phỏng, trao đổi, thảo luận về ý tưởng chính của thuật toán sắp xếp chèn.

Gợi ý đáp án

Ý tưởng của thuật toán sắp xếp chèn là thực hiện vòng lặp duyệt từ phần tử thứ hai đến cuối dãy. Sau mỗi bước lặp phần tử tương ứng sẽ được chèn vào vị trí đúng của dãy con đã sắp xếp là các phần tử phía trước vị trí đang duyệt.

Câu hỏi 1: Mô phỏng chi tiết các bước lặp sắp xếp chèn dãy A = [5, 0, 4, 2, 3]

Gợi ý đáp án

Chỉ số của dãy	0	1	2	3	4
Trước vòng lặp	5	0	4	2	3
Vòng lặp 1, i=1	Duyệt phần tử thứ 2, vì 0 nhỏ hơn 5 nên chèn 0 vào trước 5
Sau vòng lặp	0	5	4	2	3
Vòng lặp 2, i=2	Duyệt phần tử thứ 3, vì 4 lớn hơn 0 và nhỏ hơn 5 nên 4 được chèn vào trước 5
Sau vòng lặp	0	4	5	2	3
Vòng lặp 3, i=3	Duyệt phần tử thứ 4, vì 2 lớn hơn 0 và nhỏ hơn 4 nên 2 được chèn vào trước 4
Sau vòng lặp	0	2	4	5	3
Vòng lặp 4, i=4	Duyệt phần tử thứ 5, vì 3 lớn hơn 2 và nhỏ hơn 4 nên 3 được chèn vào trước 4
Kết thúc	0	2	3	4	5

Câu hỏi 2: Nếu dãy ban đầu đã được sắp xếp thì thuật toán sắp xếp chèn sẽ thực hiện như thế nào?

Gợi ý đáp án

Nếu dãy ban đầu đã được sắp xếp, thì thuật toán sắp xếp chèn sẽ không thực hiện thay đổi nào trên dãy vì mỗi phần tử trong dãy đã đứng đúng vị trí của nó. Cụ thể, các bước của thuật toán sẽ được thực hiện như sau:

Xác định phần tử đầu tiên trong dãy là phần tử thứ 2 (i = 1), không cần thực hiện bất kỳ thay đổi nào vì phần tử này đã đứng đúng vị trí của nó trong dãy đã được sắp xếp.

Kiểm tra phần tử thứ 3 (i = 2) so với các phần tử trước nó trong dãy. Nếu phần tử này đã đứng đúng vị trí, không cần thực hiện thay đổi nào.

Tiếp tục kiểm tra và so sánh từng phần tử còn lại trong dãy với các phần tử trước nó. Nếu phần tử đang xét đã đứng đúng vị trí, không cần thực hiện thay đổi nào.

Sau khi kiểm tra hết các phần tử trong dãy, thuật toán kết thúc mà không có bất kỳ thay đổi nào được thực hiện trên dãy ban đầu, vì dãy đã được sắp xếp.

2. Thuật toán sắp xếp chọn

Hoạt động 2: Quan sát sơ đồ mô phỏng, trao đổi thảo luận về ý tưởng chính của thuật toán sắp xếp chọn.

Gợi ý đáp án

Thuật toán sắp xếp chọn thực hiện một vòng lặp với chỉ số i chạy từ 0 (phần tử đầu tiên) đến n-2 (phần tử gần cuối). Tại mỗi bước lặp, chọn phần tử nhỏ nhất nằm trong dãy A[i], A[i+1],…,A[n-1] và đổi chỗ phần tử này với A[i].

Câu hỏi 1: Thực hiện mô phỏng sắp xếp theo thuật toán sắp xếp chọn dãy sau: 4, 5, 2, 1, 3.

Gợi ý đáp án

Chỉ số của dãy	0	1	2	3	4
Trước vòng lặp	4	5	2	1	3
Vòng lặp 1, i=0	1 là phần tử nhỏ nhất, đổi chỗ 1 và 4
Sau vòng lặp	1	5	2	4	3
Vòng lặp 2, i=1	2 là phần tử nhỏ nhất không tính phần tử đầu tiên, đổi chỗ 2 và 5
Sau vòng lặp	1	2	5	4	3
Vòng lặp 3, i=2	3 là phần tử nhỏ nhất không tính hai phần tử đầu tiên, đổi chỗ 3 và 5
Sau vòng lặp	1	2	3	4	5
Vòng lặp 4, i=3	4 là phần tử nhỏ nhất không tính ba phần tử đầu tiên, giữ nguyên vị trí dãy số
Kết thúc	1	2	3	4	5

Câu hỏi 2: Theo thuật toán sắp xếp chọn, sau mỗi bước thứ i thì các phần tử A[0]. A[1]..... A[i] đã được sắp xếp đúng. Đúng hay sai?

Gợi ý đáp án

Đúng. Theo thuật toán sắp xếp chọn (Selection Sort), sau mỗi bước thứ i, phần tử nhỏ nhất (hoặc lớn nhất, tùy thuật toán sắp xếp chọn làm việc với phần tử nhỏ nhất hoặc lớn nhất) trong đoạn từ A[0] đến A[i] sẽ được đưa về vị trí đúng của nó trong mảng. Nghĩa là sau mỗi bước thứ i, các phần tử A[0], A[1], ..., A[i] đã được sắp xếp đúng thứ tự so với nhau. Các phần tử A[i+1], A[i+2], ..., A[n-1] (n là số phần tử trong mảng) vẫn chưa được sắp xếp đúng thứ tự. Quá trình này tiếp tục cho đến khi tất cả các phần tử trong mảng được sắp xếp đúng thứ tự.

3. Thuật toán sắp xếp nổi bọt

Hoạt động 3: Cùng trao đổi, thảo luận về các ý tưởng của thuật toán sắp xếp nổi bọt.

Gợi ý đáp án

Thuật toán sắp xếp nổi bọt thực hiện nhiều vòng lặp, kiểm tra hai phần tử cạnh nhau, nếu chúng chưa sắp xếp đúng thì đổi chỗ.

Câu hỏi 1: Mô tả các bước thuật toán sắp xếp nổi bọt của dãy A = [4, 3, 1, 2]

Gợi ý đáp án

Vòng lặp 1
Chỉ số của dãy	0	1	2	3
Trước vòng lặp	4	3	2	1
Bước lặp 1, j=0	4	3	2	1	So sánh phần tử thứ nhất và phần tử thứ 2
Bước lặp ,2 j=1	3	4	2	1	So sánh phần tử thứ 2 và phần tử thứ 3
Bước lặp 3, j=2	3	2	4	1	So sánh phần tử thứ 3 và phần tử thứ 4
Kết thúc vòng 1	3	2	1	4
Vòng lặp 2
Chỉ số của dãy	0	1	2	3
Trước vòng lặp	3	2	1	4
Bước lặp 1, j=0	3	2	1	4	So sánh phần tử thứ nhất và phần tử thứ 2
Bước lặp ,2 j=1	2	3	1	4	So sánh phần tử thứ 2 và phần tử thứ 3
Bước lặp 3, j=2	2	1	3	4	So sánh phần tử thứ 3 và phần tử thứ 4
Kết thúc vòng 2	2	1	3	4
Vòng lặp 3
Chỉ số của dãy	0	1	2	3
Trước vòng lặp	2	1	3	4
Bước lặp 1, j=0	1	2	3	4	So sánh phần tử thứ nhất và phần tử thứ 2
Bước lặp ,2 j=1	1	2	3	4	So sánh phần tử thứ 2 và phần tử thứ 3
Bước lặp 3, j=2	1	2	3	4	So sánh phần tử thứ 3 và phần tử thứ 4
Kết thúc vòng 3	1	2	3	4
Kết thúc lặp	1	2	3	4

Câu hỏi 2: Khi nào thì các mũi tên ở tất cả các bước trong sơ đồ mô phỏng thuật toán sắp xếp nổi bọt đều có màu đỏ?

Gợi ý đáp án

Thuật toán sắp xếp nổi bọt hoạt động bằng cách so sánh các phần tử kế tiếp trong danh sách và hoán đổi chúng nếu chúng không được sắp xếp theo thứ tự. Quá trình lặp sẽ tiếp tục cho đến khi tất cả các phần tử đều được sắp xếp. Vì vậy khi màu của tất cả các mũi tên đều đỏ trong sơ đồ mô phỏng thì có nghĩa là không còn phần tử nào được sắp xếp theo thứ tự tăng dần hoặc giảm dần và không cần thực hiện bất kỳ hoán đổi nào nữa.

Luyện tập Tin học 11 Bài 21

Câu hỏi 1

Cho dãy A= [5, 8, 1, 0, 10, 4, 3]. Viết các chương trình sắp xếp dãy A theo thứ tự tăng dần theo các thuật toán sắp xếp chèn, sắp xếp chọn và sắp xếp nổi bọt.

Câu hỏi 2

Viết chương trình nhập một dãy số từ bàn phím, các số cách nhau bởi dấu cách, thực hiện sắp xếp dãy đã nhập theo một trong các thuật toán sắp xếp rồi in kết quả ra màn hình.