"Bài giảng môn Tin 7 bài 4 sách Cánh diều: Sắp xếp nổi bọt" được biên soạn với nội dung trình bày về: ý tưởng sắp xếp bằng cách đổi chỗ các phần tử liền kề; thuật toán sắp xếp nổi bọt; vận dụng kiến thức để giải các bài tập thực hành. Mời quý thầy cô và các em cùng tham khảo chi tiết tại đây. | BÀI 4 SẮP XẾP NỔI BỌT MỞ ĐẦU Làm thế nào để cho máy tính biết một dãy đã có thứ tự tăng dần Để máy tính biết một dãy đã có thứ tự tăng dần ta phải sắp xếp theo thứ tự để máy tính có thể nhận dạng. HOẠT ĐỘNG 1 Giả sử có một dãy hộp kẹo mỗi hộp chứa một số kẹo nào đó. Có một chú robot chỉ biết làm hai thao tác So sánh số kẹo trong hai hộp cạnh nhau Hoán đổi vị trí hai hộp kẹo cạnh nhau Theo em chú robot phải làm thế nào để xếp lại các hộp sao cho số kẹo trong các hộp tăng dần Chú robot phải so sánh lần lượt các hộp kẹo cạnh nhau ở trong dãy nếu hộp kẹo thứ nhất lớn hơn hộp kẹo thứ hai thì tiến hành hoán đổi vị trí hai hộp kẹo cạnh nhau. Robot cứ thức hiện lần lượt cho đến khi không đổi chỗ các hộp kẹo cạnh nhau nữa thì kết thúc công việc. 1. Ý tưởng sắp xếp bằng cách đổi chỗ các phần tử liền kề Ví dụ Cho dãy 5 hộp kẹo với số lượng kẹo trong mỗi hộp khác nhau tương ứng là 5 1 4 2 8 Minh họa Giải thích Ở lượt thứ nhất so sánh hai hộp đầu tiên nếu số kẹo ở hộp đứng trước lớn hơn số kẹp ở hộp đứng sau thì đổi vị trí hai hộp này cho nhau. Tiếp tục như vậy cho đến hết dãy là hết một lượt gt ta thu được hộp cuối là hộp chứa nhiều kẹo nhất Tiếp tục các lượt thứ hai thứ ba theo cách trên cứ lặp lại như vậy cho đến khi gặp một lượt mà suốt cả lượt đó robot không phải đổi chỗ hai hộp nào thì dãy đã được sắp xếp xong. HOẠT ĐỘNG 2 Với dãy số đã cho ở ví dụ trên em hãy thực hiện thuật toán được mô tả ở dưới và cho biết đó có phải là thuật toán sắp xếp nổi bọt hay không Lặp khi dãy chưa sắp xếp xong đúng a Thực hiện một lượt so sánh các cặp phần tử liền kề và đổi chỗ khi trái thứ tự tăng dần b Nếu trong lượt vừa thực hiện xong không có đổi chỗ dãy chưa sắp xếp xong sai Hết nhánh Hết lặp Thuật toán được mô tả như hình trên là thuật toán sắp xếp nổi bọt. 2. Thuật toán sắp xếp nổi bọt Ở mỗi lượt robot thực hiện Xuất phát từ đầu dãy i 1 xét cặp a1 a2 nếu a1 gt a2 trái thứ tự mong muốn thì đổi chỗ cho nhau trái lại không cần làm gì. Dịch sang phải một vị trí xét cặp a2 a3 so sánh và .
