Tải bài giảng điện tử powerpoint Khoa học máy tính 11 KNTT tri thức Bài 21: Các thuật toán sắp xếp đơn giản. Bài học được thiết kể đẹp mắt, nội dung giảng dạy hay nhiều trò chơi và video phong phú thu hút học sinh tập trung nắm bắt kiến thức quan trong. Tải Tải giáo án Powerpoint Powerpoint tải về chỉnh sửa được. Kéo xuống để xem chi tiết
Rõ nét về file powerpoint trình chiếu. => Xem thêm
CHÀO MỪNG CẢ LỚP ĐẾN VỚI BÀI HỌC MỚI!
KHỞI ĐỘNG
Bài toán sắp xếp cơ bản có dạng như sau:
Cho dãy A gồm n phần tử: A[0], A[1],…, A[n-1] (1)
Cần sắp xếp dãy theo thứ tự tăng dần: A[0] ≤ A[1] ≤ … ≤ A[n-1] (2)
Em hãy trình bày ý tưởng của mình để giải bài toán sắp xếp với dãy có bốn phần tử.
BÀI 21: CÁC THUẬT TOÁN SẮP XẾP ĐƠN GIẢN
NỘI DUNG BÀI HỌC
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
01 THUẬT TOÁN SẮP XẾP CHÈN
Hoạt động 1: Tìm hiểu ý tưởng thuật toán sắp xếp chèn
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.
Cho dãy A = [5, 3, 9, 7, 2].
Dựa vào sơ đồ mô phỏng và trả lời các câu hỏi sau:
GHI NHỚ
Ý 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
Câu hỏi củng cố kiến thức
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?
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.
02 THUẬT TOÁN SẮP XẾP CHỌN
Hoạt động 2: Tìm hiểu ý tưởng thuật toán sắp xếp chọn
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.
Bài toán: Xét dãy A = [5, 3, 9, 7, 2]. Quan sát sơ đồ Hình 21.2 SGK trang 101 và trả lời các câu hỏi:
Hình 21.2. Mô phỏng thuật toán sắp xếp chọn
MỞ RỘNG:
Video sau đây hướng dẫn sắp xếp số hạng trong dãy số bằng cách sắp xếp chọn.
GHI NHỚ
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ể mô tả bằng hàm SelectSort(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]
Câu hỏi củng cố kiến thức
.....
=> Còn nữa.... Files tải về, sẽ có đầy đủ nội dung bài học
Nâng cấp lên tài khoản VIP để tải tài liệu và dùng thêm được nhiều tiện ích khác
Bài giảng điện tử Khoa học máy tính 11 KNTT, Tải giáo án Powerpoint Khoa học máy tính 11 KNTT Bài 21: Các thuật toán sắp xếp đơn, Tải giáo án Powerpoint Khoa học máy tính 11 KNTT tri thức Bài 21: Các thuật toán sắp xếp đơn