Slide bài giảng 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

Tóm lược nội dung

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

KHỞI ĐỘNG

- GV dẫn dắt, đặt vấn đề cho HS: Bài học trước đã cho em thấy rằng việc tìm kiếm trên một dãy đã được sắp xếp nhanh hơn so với tìm kiếm tuần tự. Do đó, bài toán tìm kiếm có mối liên hệ chặt chẽ với bài toán sắp xếp.

NỘI DUNG BÀI HỌC GỒM

• Tìm hiểu về thuật toán sắp xếp chèn

•  Tìm hiểu về thuật toán sắp xếp chọn

•  Tìm hiểu về thuật toán sắp xếp nổi bọt

• Luyện tập

• Vận dụng

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.

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

Câu 1: Cho dãy số a như hình dưới đây

Sử dụng thuật toán sắp xếp chọn để sắp xếp dãy số theo thứ tự giảm 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 2: Thuật toán sắp xếp nổi bọt sắp xếp danh sách bằng cách?

A. Chọn phần tử có giá trị bé nhất đặt vào đầu danh sách

B. Chọn phần tử có giá trị lớn nhất đặt vào đầu danh sách

C. Hoán đổi nhiều lần các giá trị liền kề nếu giá trị của chúng không đúng thứ tự.

D. Chèn phần tử vào vị trí thích hợp để đảm bảo danh sách theo đúng thứ tự.

Câu 3:Thuật toán sắp xếp chọn sẽ so sánh các phần tử ở vị trí nào?

A. So sánh phần tử ở vị trí được xét với các phần tử phía trước.

B. So sánh phần tử ở vị trí được xét với các phần tử phía sau.

C. So sánh phần tử ở vị trí được xét với các phần tử liền kề.

D. So sánh phần tử ở vị trí được xét với các phần tử đầu tiên.

Câu 4. Mô tả thuật toán sắp xếp nổi bọt 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 5. Thuật toán sắp xếp nổi bọt có thể sắp xếp danh sách theo thứ tự? 

A. Tăng dần

B. Giảm dần

C. Tăng dần hoặc giảm dần

D. Cả A, B, C đều sai.

Đáp án gợi ý:

Câu 1: D

Câu 2: C 

Câu 3: B

Câu 4: C 

Câu 5: C

HOẠT ĐỘ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.