Giáo án và PPT Tin học 7 cánh diều Bài 4: Sắp xếp nổi bọt

BÀI 4: SẮP XẾP NỔI BỌT

HOẠT ĐỘNG KHỞI ĐỘNG

GV nêu vấn đề: Làm thế nào để cho máy tính biết một dãy đã có thứ tự tăng dần?

HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC

Hoạt động 1: Ý tưởng sắp xếp bằng cách đổi chỗ các phần tử liền kề 

GV nêu ví dụ về bài toán sắp xếp: 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?

Sản phẩm dự kiến:

- 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à:

- Minh họa ý tưởng

- 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 

=> 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: Tìm hiểu thuật toán sắp xếp nổi bọt 

GV yêu cầu HS thảo luận nhóm đôi,  nghiên cứu mục 2 trong SGK – tr88trình bày lại về thuật toán sắp xếp nổi bọt trong ví dụ ở mục 1.

Sản phẩm dự kiến:

- Xuất phát từ đầu dãy, i = 1, xét cặp (a₁, a₂), nếu a₁ > a₂ (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 (a₂, a₃); so sánh và đổi chỗ nếu cần

- Quá trình tiếp tục, dịch sang phải một vị trí, xét cặp (a_i+1, a_i+2) so sánh và đổi chỗ nếu cần.

- Khi hết dãy thì xong một lượt xét các cặp số kề nhau để đổi chỗ.

- Thực hiện nhiều lượt như trên cho đến khi không còn bất kì cặp liền kề (a_i, a_i+1) nào trái thứ tự mong muốn, ta được dãy đã sắp xếp.

Chú ý: 

+ Sau lượt đổi chỗ thứ nhất, giá trị lớn nhất của dãy số đã ở cuối dãy, đúng vị trí cuối cùng của nó

+ Chỉ một lượt đổi chỗ chưa đảm bảo dãy có thứ tự tăng dần.

HOẠT ĐỘNG LUYỆN TẬP

Khoanh tròn vào đáp án đặt trước câu trả lời đúng

Câu 1. Trong thuật toán sắp xếp nổi bọt thì dấu hiệu để biết dãy chưa sắp xếp xong là:

A. Vẫn còn cặp phần tử liền kề không đúng thứ tự mong muốn.

B. Không còn cặp phần tử nào cần đổi chỗ.

C. Chưa xét đến phần tử cuối cùng.

D. Chưa đủ số lần đổi chỗ.

Câu 2. Cho dãy 2, 4, 3, 8, 9. Để sắp xếp dãy tăng dần theo thuật toán sắp xếp nổi bọt, phần tử 9 có bao nhiêu lần đổi chỗ?

A. 0                      B. 1                      C. 2                      D. 3

Câu 3. Trong thuật toán sắp xếp nổi bọt, khi nào hai phần tử liền kề được đổi chỗ?

A. Khi hai phần tử liền kề nằm đúng với thứ tự mong muốn.

B. Khi hai phần tử liền kề nằm chưa đúng với thứ tự mong muốn.

C. Khi các phần tử liền kề đã nằm đúng với thứ tự mong muốn.

D. Tất cả đều sai.

Câu 4. Điền vào dấu …trong phát biểu sau: “Trong thuật toán sắp xếp nổi bọt lặp khi có cặp phần tử trái thứ tự mong muốn thì đổi chỗ cho nhau, trái lại thì không cần làm gì. Sau đó …..một vị trí để xét cặp tiếp theo, so sánh và đổi chỗ nếu cần.”

A. Dịch sang phải.

B. Dịch sang trái.

C. Chuyển về vị trí đầu tiên.

D. Chuyển đến vị trí cuối cùng..

Câu 5. Để sắp xếp dãy 1, 4, 2, 6 theo thứ tự tăng dần bằng thuật toán nổi bọt thì có bao nhiêu lần đổi chỗ hai phần tử liền kề:

A. 0                      B. 1                                C. 2                      D. 3:

Sản phẩm dự kiến:

HOẠT ĐỘNG VẬN DỤNG

Câu 1. 

1) Trong thuật toán sắp xếp nổi bọt thì dấu hiệu để biết dãy chưa sắp xếp xong là gì?

2) Theo em, có phải hình bên đã mô tả chi tiết một lượt robot thực hiện so sánh các cặp phần tử liền kề và đổi chỗ khi chúng trái thứ tự mong muốn không?

Câu 2. Theo em, vì sao thuật toán sắp xếp trên lại có tên là sắp xếp nổi bọt?