Giáo án tích hợp AI Tin học 11 KHMT 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

I. NỘI DUNG CHI TIẾT BÀI HỌC

• THUẬT TOÁN SẮP XẾP CHÈN: Là thuật toán thực hiện chèn từng phần tử vào đúng vị trí trong một dãy con đã được sắp xếp.

  • Quy tắc: Duyệt từ phần tử thứ hai đến cuối dãy, với mỗi phần tử, so sánh và chèn nó vào vị trí thích hợp giữa các phần tử đã duyệt.

  • Ví dụ: Với dãy [5, 3, 9], phần tử 3 được so sánh với 5 và chèn lên trước tạo thành [3, 5, 9].

• THUẬT TOÁN SẮP XẾP CHỌN: Là thuật toán thực hiện tìm phần tử nhỏ nhất trong dãy chưa sắp xếp và đổi chỗ nó với phần tử đầu tiên của dãy đó.

  • Quy tắc: Duyệt qua dãy, tại mỗi bước chọn phần tử nhỏ nhất và đưa về vị trí đúng.

  • Ví dụ: Dãy [5, 3, 9, 2], chọn 2 đổi chỗ với 5 để có [2, 3, 9, 5].

• THUẬT TOÁN SẮP XẾP NỔI BỌT: Là thuật toán so sánh các cặp phần tử liền kề và đổi chỗ chúng nếu chưa đúng thứ tự.

  • Quy tắc: Sau mỗi lượt duyệt, phần tử lớn nhất sẽ "nổi" lên vị trí cuối cùng của dãy.

  • Ví dụ: So sánh [5, 3] trong [5, 3, 9], vì 5 > 3 nên đổi chỗ thành [3, 5, 9].

II. KIẾN THỨC TRỌNG TÂM

1. Bài toán sắp xếp là nền tảng để tối ưu hóa bài toán tìm kiếm.

2. Sắp xếp chèn hiệu quả khi dữ liệu đã có một phần thứ tự nhất định.

3. Sắp xếp chọn ưu tiên việc chọn phần tử nhỏ nhất đưa về đúng vị trí đầu.

4. Sắp xếp nổi bọt dựa trên nguyên lý đổi chỗ các cặp liền kề liên tục.

5. Cả ba thuật toán đều sử dụng cấu trúc vòng lặp để duyệt và xử lý dữ liệu.

6. Hiệu quả của thuật toán sắp xếp phụ thuộc vào số lượng phép so sánh và đổi chỗ.

III. BỐ CỤC SLIDE PPTX

• Slide 1: Tiêu đề

  • Tiêu đề: BÀI 21: CÁC THUẬT TOÁN SẮP XẾP ĐƠN GIẢN

  • Nội dung: Giới thiệu tầm quan trọng của việc sắp xếp dữ liệu.

• Slide 2: Thuật toán sắp xếp chèn

  • Tiêu đề: THUẬT TOÁN SẮP XẾP CHÈN

  • Nội dung: Ý tưởng chèn phần tử vào dãy đã có thứ tự.

• Slide 3: Minh họa sắp xếp chèn

  • Tiêu đề: CÁC BƯỚC CỦA SẮP XẾP CHÈN

  • Nội dung: Ví dụ mô phỏng quá trình chèn từng phần tử.

• Slide 4: Thuật toán sắp xếp chọn

  • Tiêu đề: THUẬT TOÁN SẮP XẾP CHỌN

  • Nội dung: Ý tưởng tìm và đưa phần tử nhỏ nhất về vị trí đúng.

• Slide 5: Minh họa sắp xếp chọn

  • Tiêu đề: CÁC BƯỚC CỦA SẮP XẾP CHỌN

  • Nội dung: Ví dụ mô phỏng đổi chỗ phần tử nhỏ nhất.

• Slide 6: Thuật toán sắp xếp nổi bọt

  • Tiêu đề: THUẬT TOÁN SẮP XẾP NỔI BỌT

  • Nội dung: Ý tưởng so sánh và đổi chỗ các cặp liền kề.

• Slide 7: So sánh và tổng kết

  • Tiêu đề: TỔNG KẾT CÁC THUẬT TOÁN

  • Nội dung: Bảng so sánh đặc điểm chính của ba thuật toán.