Soạn mới giáo án Khoa học máy tính 11 kết nối tri thức bài 21: Các thuật toán sắp xếp đơn giản

HOẠT ĐỘNG CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

Bước 1: GV chuyển giao nhiệm vụ:

- GV đặt vấn đề theo Hoạt động 1 trang 99 SGK: 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.

- GV chiếu sơ đồ các bước thực hiện thuật toán sắp xếp chèn (hình 21.1) cho HS quan sát.

- GV yêu cầu HS quan sát sơ đồ mô phỏng và trả lời các câu hỏi sau:

+ So sánh số bước lặp với độ dài của dãy số ban đầu.

+ Vị trí xuất phát của mũi tên màu đỏ có quan hệ gì với chỉ số bước lặp?

+ Khi kết thúc lặp ta thu được kết quả gì?

- Trên cơ sở kiến thức vừa nêu, GV yêu cầu HS nêu ý tưởng chính của thuật toán sắp xếp chèn.

- GV giới thiệu hai cách mô tả thuật toán sắp xếp chèn trên thực tế.

- Dựa vào ví dụ vừa nêu ở Hoạt động 1, GV yêu cầu HS trả lời câu hỏi củng cố trang 100 SGK:

+ Câu 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].

+ Câu 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?

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

- HS thảo luận nhóm, đọc SGK và trả lời câu hỏi.

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

- Đại diện nhóm HS trình bày.

*Câu hỏi củng cố trang 100 SGK:

+ Câu 1: Mô tả thuật toán sắp xếp chèn với dãy [5, 0, 4, 2, 3] có thể như sau:

Bước 1. Chèn phần tử 0 vào trước 5, dãy thu được: [0, 5, 4, 2, 3]

Bước 2. Chèn phần tử 4 vào trước 5, thu được: [0, 4, 5, 2, 3]

Bước 3. Chèn phần tử 2 vào trước 4, thu được:  [0, 2, 4, 5, 3].

Bước 4. Chèn phần tử 3 vào trước 4, thu được: [0, 2, 3, 4, 5].

+ Câu 2: Nếu dãy ban đầu đã được sắp xếp đúng thì tại mỗi bước duyệt không cần thực hiện thao tác "chèn" nữa vì A[i] đã ở đúng vị trí rồi. Do vậy, thuật toán sắp xếp chèn sẽ không thực hiện bất cứ thao tác gì trên dãy đã cho.

- Các nhóm khác nhận xét, bổ sung cho nhóm bạn.

Bước 4: Đánh giá kết quả thực hiện:

- GV nhận xét, đánh giá kết quả thảo luận của HS.

1. Thuật toán sắp xếp chè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.

- Thuật toán sắp xếp chèn có thể mô tả bằng hàm InsertSort(A) như sau:

1 deft InsertionSort(A):

2    n = len(A)

3    for i in range(1,n):

4         value = A[i]

5         j = i – 1

6         while j >= 0 and A[j] > value:

7             A[j+1] = A[j]

8             j = j – 1

9         A[j+1] = value

HOẠT ĐỘNG CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

Bước 1: GV chuyển giao nhiệm vụ:

- GV đặt vấn đề theo Hoạt động 2 trang 100 SGK: 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.

- GV chiếu sơ đồ các bước thực hiện thuật toán sắp xếp chọn (hình 21.2) cho HS quan sát.

- GV yêu cầu HS quan sát sơ đồ mô phỏng và trả lời các câu hỏi sau:

Xét dãy A = [5, 3, 9, 7, 2]. Sơ đồ sau mô phỏng các bước thực hiện thuật toán sắp xếp chọn. Quan sát sơ đồ và trả lời các câu hỏi sau:

1) Có bao nhiêu vòng lặp? Chỉ số i bắt đầu bằng bao nhiêu?

2) Tại mỗi vòng lặp đều có một thao tác đổi chỗ hai phần tử, đó là các phần tử nào?

3) Khi kết thúc vòng lặp ta thu được kết quả gì?

- Trên cơ sở kiến thức vừa nêu, GV yêu cầu HS nêu ý tưởng chính của thuật toán sắp xếp chọn.

- Dựa vào ví dụ vừa nêu ở Hoạt động 2, GV yêu cầu HS trả lời câu hỏi củng cố trang 102 SGK:

+ Câu 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.

+ Câu 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?

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

- HS thảo luận nhóm, đọc SGK và trả lời câu hỏi.

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

- Đại diện nhóm HS trình bày.

*Câu hỏi củng cố trang 102 SGK

+ Câu 1: Mô tả tường minh thuật toán sắp xếp chọn với dãy [4, 5, 2, 1, 3]. Các bước thực hiện như sau:

Bước 1. Tìm phần tử nhỏ nhất bên phải 4, số đó là 1, đổi chỗ cho 4. Dãy thu được [1, 5, 2, 4, 3].

Bước 2. Tìm phần tử nhỏ nhất bên phải 5, số đó là 2, đổi chỗ cho 5. Dãy thu được [1, 2, 5, 4, 3].

Bước 3. Tìm phần tử nhỏ nhất bên phải 5, số đó là 3, đổi chỗ cho 5. Dãy thu được [1, 2, 3, 4, 5].

Bước 4. Tìm phần tử nhỏ nhất bên phải 4, không tìm thấy. Dãy thu được [1, 2, 3, 4, 5].

+ Câu 2: Đúng. Sau mỗi bước thứ i thì dãy con A[0], A[1],…,A[i] đã được sắp xếp đúng.

- Các nhóm khác nhận xét, bổ sung cho nhóm bạn.

Bước 4: Đánh giá kết quả thực hiện:

- GV nhận xét, đánh giá kết quả thảo luận của HS.

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

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

- Thuật toán sắp xếp chọn có thể được mô tả bằng hầm SelectionSort(A) như sau:

1 def SelectionSort(A):

2    n = len(A)

3    for i in range(n-1):

4         iMin = i

5         for j in range(i+1,n):

6             if A[j] < A[iMin]:

7                  iMin = j

8         A[i],A[iMin] = A[iMin],A[i]

HOẠT ĐỘNG CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

Bước 1: GV chuyển giao nhiệm vụ:

- GV đặt vấn đề theo Hoạt động 3 trang 102 SGK: 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.

- GV chiếu sơ đồ các bước thực hiện thuật toán sắp xếp nổi bọt (hình 21.3) cho HS quan sát.

- GV yêu cầu HS quan sát sơ đồ mô phỏng và trả lời các câu hỏi sau:

+ Nêu ý tưởng chính của thuật toán sắp xếp nổi bọt.

- Trên cơ sở kiến thức vừa nêu, GV yêu cầu HS nêu ý tưởng chính của thuật toán sắp xếp nổi bọt.

- Dựa vào ví dụ vừa nêu ở Hoạt động 3, GV yêu cầu HS trả lời câu hỏi củng cố trang 103 SGK:

+ Câu 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].

+ Câu 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 đỏ?

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

- HS thảo luận nhóm, đọc SGK và trả lời câu hỏi.

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

- Đại diện nhóm HS trình bày.

+ Câu 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].

Pha 1. Duyệt một lượt từ trái sang phải, nấu hai phần tử cạnh nhau xếp không đúng thì đổi vị trí, cuối cùng thu được dãy [3, 1, 2, 4].

Pha 2. Làm lại tương tự bước trên, nhưng chỉ duyệt 3 phần tử, thu được dãy [1, 2, 3, 4].

Pha 3. Không cần đổi chỗ vì 1, 2 đã sắp xếp đúng vị trí.

+ Câu 2: Trong sơ đồ như hình 21.3 trong SGK, nếu dãy ban đầu sắp xếp theo thứ tự giảm dần thì ở tất cả các bước đều có màu đỏ trong sơ đồ.

- Các nhóm khác nhận xét, bổ sung cho nhóm bạn.

Bước 4: Đánh giá kết quả thực hiện:

- GV nhận xét, đánh giá kết quả thảo luận của HS.

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

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

- 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ó nhiều cách thể hiện thuật toán này, nhưng cách thường sử dụng hai vòng lặp lồng nhau, vòng lặp trong thực hiện thao tác đổi chỗ hai phần tử cạnh nhau cho đến khi dãy được sắp xếp xong.

- Thuật toán sắp xếp nổi bọt được mô tả bằng hàm BubbleSort(A) như sau:

1 def BubbleSort(A):

2    n = len(A)

3    for i in range(n-1):

4         for j in range(n-1-i):

5             if A[j] > A[j+1]:

6    A[j],A[j+1]=A[j+1],A[j]