BÀI 21. CÁC THUẬT TOÁN SẮP XẾP ĐƠN GIẢN
Trang bìa
Trang bìa
Ảnh
TIN HỌC 11
BÀI 21. CÁC THUẬT TOÁN SẮP XẾP ĐƠN GIẢN
Ảnh
Mục tiêu bài học
Mục tiêu
Ảnh
Mục tiêu:
Biết và thực hiện được một số thuật toán sắp xếp đơn giản.
Khởi động
Khởi động
Ảnh
- 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 A theo thứ tự tăng dần: A[0] latex(<=) A[1] latex(<=) ... latex(<=) 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ử.
Hình thành kiến thức
1. Thuật toán sắp xếp chèn
1. 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.
Ảnh
- Hoạt động 1: Tìm hiểu ý tưởng thuật toán sắp xếp chèn
Ảnh
- Nhiệm vụ
- Nhiệm vụ:
Cho dãy A = [5, 3, 9, 7, 2]. Sơ đồ sau mô phỏng các bước của thuật toán sắp xếp chèn.
Ảnh
- Câu hỏi (- Nhiệm vụ)
Ảnh
- Câu hỏi:
1) So sánh số bước lặp với độ dài của dãy số ban đầu. 2) 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? 3) Khi kết thúc lặp ta thu được kết quả gì?
- Tìm hiểu
- Tìm hiểu:
Ảnh
Thao tác "chèn" A[i] vào vị trí đúng trong dãy con A[0], A[1], ..., A[i - 1] có thể được mô tả bằng cách "nhấc" A[i] lên và chuyển các phần tử bên trái A[i] nhưng lớn hơn A[i] sang phải, sau đó đặt A[i] vào vị trí đúng.
Ảnh
- Mô tả thuật toán sắp xếp chèn
- Mô tả thuật toán sắp xếp chèn:
Ảnh
Thuật toán sắp xếp chèn có thể mô tả bằng hàm insertionSort(A) như sau:
- Ghi nhớ
- Ghi nhớ:
Ả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í trước vị trí đang duyệt.
- Câu hỏi củng cố
Ảnh
- Câu hỏi củng 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?
2. Thuật toán sắp xếp chọn
2. 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
Ảnh
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.
- Nhiệm vụ
- Nhiệm vụ:
Ảnh
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âu hỏi: 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ì?
- Hình 21.2
Ảnh
- Tìm hiểu
Ảnh
Thuật toán sắp xếp chọn: chỉ số i chạy từ 0 đến n - 2. Tại mỗi bước lặp, tìm phần tử nhỏ nhất trong dãy A[i], A[i + 1], A[n - 1] và đổi chỗ phần tử nhỏ nhất này với A[i].
- Tìm hiểu:
- Mô tả thuật toán chọn
- Mô tả thuật toán chọn như sau:
Ảnh
Ảnh
- Bước chọn phần tử tại dòng 2 và đổi chỗ tại dòng lệnh 3:
Ảnh
- Thuật toán sắp xếp chọn có thể mô tả bằng hàm insertionSort(A) như sau:
- Thuật toán sắp xếp chọn có thể mô tả bằng hàm insertionSort(A):
Ảnh
Ảnh
- Ghi nhớ
- Ghi nhớ:
Ả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].
- Câu hỏi củng cố
Ảnh
- Câu hỏi củng cố:
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?
3. Thuật toán sắp xếp nổi bọt
Ảnh
3. Thuật toán sắp xếp nổi bọt
- HĐ3: Tìm hiểu các ý tưởng thuật toán sắp xếp nổi bọt
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.
- Tìm hiểu
Ảnh
- Tìm hiểu:
Thuật toán sắp xếp nổi bọt là liên tục đổi chỗ hai phần tử cạnh nhau nếu chúng chưa được sắp thứ tự đúng. Thuật toán này sẽ thực hiện nhiều vòng lặp. Chỉ số j chạy từ 0 đến n - 2 và kiểm tra hai phần tử liền nhau A[j], A[j+1], nếu chúng chưa sắp thứ tự đúng thì đổi chỗ.
Ảnh
+ tiếp (- Tìm hiểu)
Ảnh
Ảnh
Vòng lặp đầu tiên của thuật toán nổi bọt để thấy sau vòng lặp này, phần tử lớn nhất được chuyển về cuối dãy A.
+ tiếp (- Tìm hiểu)
Ảnh
Ý tưởng của thuật toán nổi bọt: liên tục đổi chỗ hai phần tử cạnh nhau nếu chúng chưa được sắp thứ tự đúng.
Chỉ số j chạy từ 0 đến n-2 và kiểm tra hai phần tử liền nhau A[j], A[j+1], nếu chưa sắp thứ tự đúng thì đổi chỗ. Sau mỗi vòng lặp, phần tử lớn nhất được chuyển về cuối dãy. Không cần đủ n-1 bước lặp, với chỉ số i, vòng lặp ở dòng 2 chỉ cần n-1-i bước lặp.
Ảnh
+ tiếp (- Tìm hiểu)
Thuật toán sắp xếp chọn có thể mô tả bằng hàm BubbleSort(A):
Ảnh
Ảnh
- Ghi nhớ
- Ghi nhớ:
Ảnh
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 dùng là 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âu hỏi củng cố
Ảnh
- Câu hỏi củng cố:
Ảnh
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 đỏ?
Luyện tập & Vận dụng
- Luyện tập
Ảnh
- Luyện tập
1. Cho dãy A= [5, 8, 1, 0, 10, 4, 3]. Viết các chương trình sắp xếp dãy A theo thứ tự tăng dần theo các thuật toán sắp xếp chèn, sắp xếp chọn và sắp xếp nổi bọt. 2. Viết chương trình nhập một dãy số từ bàn phím, các số cách nhau bởi dấu cách, thực hiện sắp xếp dãy đã nhập theo một trong các thuật toán sắp xếp rồi in kết quả ra màn hình.
Vận dụng
- Vận dụng
Ảnh
- Vận dụng:
1. Viết lại các thuật toán sắp xếp trong bài theo thứ tự giảm dần. 2. Nêu ý nghĩa thực tế của các thuật toán sắp xếp đã học, chẳng hạn sắp xếp các học Sinh trong lớp theo chiều cao tăng dần.
Dặn dò
Dặn dò
Ảnh
Dặn dò:
Ôn lại kiến thức vừa học. Làm bài tập trong SBT. Chuẩn bị bài sau: "Bài 22. Thực hành bài toán sắp xếp".
Cảm ơn
Ảnh