Giáo án và PPT Khoa học máy tính 11 kết nối Bài 21: Các thuật toán sắp xếp đơn giản

BÀI 21: CÁC THUẬT TOÁN SẮP XẾP ĐƠN GIẢN

A. KHỞI ĐỘNG

- GV dẫn dắt, đặt vấn đề cho HS: Bài học trước cho em thấy việc tìm kiếm trên một dãy đã sắp xếp nhanh hơn so với việc tìm kiếm tuần tự. Vì vậy bài toán tìm kiếm liên quan mật thiết đến bài toán sắp xếp. 

B. HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC

Hoạt động 1: Tìm hiểu về 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.

Hoạt động 2: Tìm hiểu về thuật toán sắp xếp chọ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].

Hoạt động 3: Tìm hiểu về 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.

C. HOẠT ĐỘNG LUYỆN TẬP, THỰC HÀNH

Câu 1: Thuật toán sắp xếp nổi bọt sắp xếp danh sách bằng cách hoán đổi các phần tử liền kề bao nhiêu lần?

A. Một lần.

B. Hai lần.

C. Mười lần.

D. Nhiều lần.

Câu 2: Cho dãy số: 15, 1, 31, 9, 78, 42. Nếu sử dụng thuật toán sắp xếp nổi bọt để sắp xếp dãy trên tăng dần thì sau bao nhiêu lượt đổi chỗ thì thuật toán kết thúc?

A. 2 

B. 3

C. 4

D. 5

Câu 3: Mô tả thuật toán sắp xếp chọn bằng ngôn ngữ tự nhiên gồm có mấy bước?

A. 2

B. 3

C. 4

D. 5

Câu 4: Sau vòng lặp thứ nhất của thuật toán sắp xếp chọn, phương án nào đúng?

A. Phần tử có giá trị nhỏ nhất trong dãy được tìm thấy và đổi chỗ cho phần tử đứng đầu dãy.

B. Phần tử có giá trị lớn nhất trong dãy được tìm thấy và đổi chỗ cho phần tử đứng đầu dãy.

C. Các phần tử liền kề được hoán đổi.

D. Phần tử có giá trị nhỏ nhất sẽ đổi vị trí cho phần tử cuối dãy.

Câu 5: Thuật toán sắp xếp chèn có thể mô tả bằng hàm nào?

A. BubbleSort(A).

B. InsertionSort(A).

C. SelectionSort(A).

D. BinarySearch(A,K).

Sản phẩm dự kiến:

Câu 1: D

Câu 2: C 

Câu 3: C

Câu 4: A 

Câu 5: B

D. HOT ĐỘNG VẬN DỤNG

- GV yêu cầu HS hoàn thành bài tập phần Vận dụng trang 103 SGK.