Giáo án và PPT Tin học 7 kết nối Bài 16: Thuật toán sắp xếp

BÀI 16: THUẬT TOÁN SẮP XẾP 

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

GV yêu cầu HS thảo luận và trả lời:

Có hai chất lỏng khác màu là xanh và đỏ, lần lượt được chứa trong hai chiếc cốc A và B (Hình 16.1a). Chúng ta cần đổi chỗ hai chất lỏng này, sao cho cốc A đựng chất lỏng màu đỏ, còn cốc B đựng chất lỏng màu xanh. Để thực hiện công việc này, chúng ta sử dụng thêm một chiếc cốc thứ ba (cốc C) không đựng gì. Em hãy quan sát Hình 16.1b, Hình 16. 1c, Hình 16.1d để biết cách thực hiện.

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

Hoạt động 1. Tìm hiểu thuật toán sắp xếp nổi bọt

GV cho học sinh hoạt động thảo luận nhóm và trả lời câu hỏi: 

Hãy viết các bước thực hiện thuật toán sắp xếp nổi bọt?

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

Mô tả thuật toán sắp xếp nổi bọt bằng ngôn ngữ tự nhiên:

- Bước 1. Với vị trí đầu tiên, em thực hiện một vòng lặp như sau:

          + So sánh hai phần tử đứng cạnh nhau theo thứ tự từ cuối dãy lên vị trí đầu tiên.

          + Nếu phần tử đứng sau nhỏ hơn phần tử đứng trước thì đổi chỗ chúng cho nhau

          + Cuối vòng lặp em sẽ nhận được dãy số với phần tử nhỏ nhất nổi lên vị trí đầu tiên

- Bước 2. Với vị trí thứ hai, em thực hiện một vòng lặp tương tự như trên

          + So sánh hai phần tử đứng cạnh nhau theo thứ tự từ cuối dãy lên vị trí thứ hai.

          + Nếu phần tử đứng sau nhỏ hơn phần tử đứng trước thì đổi chỗ chúng cho nhau

          + Cuối vòng lặp em sẽ nhận được dãy số với phần tử nhỏ thứ nhỉ lên lên vị trí thứ hai

- Bước 3. Tương tư như trên các vị trí thứ ba, thứ tư,… đến vị trí trước vị trí cuối cùng

- Bước 4. Kết thúc, em sẽ nhận được dãy số đã được sắp xếp theo thứ tự từ nhỏ đến lớn

Hoạt động 2. Tìm hiểu thuật toán sắp xếp chọn

GV cho học sinh hoạt động thảo luận nhóm và trả lời câu hỏi: 

Hãy viết các bước thực hiện thuật toán sắp xếp nổi chon?

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

Mô tả thuật toán sắp xếp chọn bằng ngôn ngữ tự nhiên

- Bước 1. Với vị trí đầu tiên, em thực hiện một vòng lặp như sau

          + So sánh từng phần tử (kể từ vị trí thứ hai đến vị trí cuối cùng) với phần tử tại vị trí đầu tiên

          + Nếu phần tử được xét nhỏ hơn phần tử tại vị trí đầu tiên thì hoán đổi nó với phần tử tại vị trí đầu tiên

          + Cuối vòng lặp, em sẽ nhận được dãy số với phần tử nhỏ nhất được đưa về vị trí đầu tiên

- Bước 2. Với vị trí thứ hai, em thực hiện một vòng lặp tương tự như trên

          + So sánh từng phần tử (kể từ vị trí thứ ba đến vị trí cuối cùng) với phần tử tại vị trí thứ hai

          + Nếu phần tử được xét nhỏ hơn phần tử tại vị trí thứ hai thì hoán đổi nó với phần tử tại vị trí thứ hai

          + Cuối vòng lặp, em sẽ nhận được dãy số với phần tử từ nhỏ thứ nhì được đưa về vị trí thứ hai

- Bước 3. Tương tư như trên các vị trí thứ ba, thứ tư,… đến vị trí trước vị trí cuối cùng

- Bước 4. Kết thúc, em sẽ nhận được dãy số đã được sắp xếp theo thứ tự từ nhỏ đến lớn

Hoạt động 3. Tìm hiểu chia bài toán thành những bài toán nhỏ hơn

- Ý nghĩa: Để giải quyết một bài toán, chúng ta đã dựa trên lời giải của bài toán nhỏ hơn. Việc chia một bài toán thành những bài toán nhỏ hơn giúp việc giải bài toán đó dễ dàng hơn, đồng thời việc mô tả thuật toán dễ hiểu và dễ thực hiện hơn

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

Từ nội dung bài học, GV yêu cầu HS hoàn thành các bài tập trắc nghiệm sau:

Câu 1: Thuật toán sắp xếp nổi bọt sắp xếp danh sách bằng cách nào?

A. Thay thế.

B. Thay đổi.

C. Hoán đổi.

Câu 2: Thuật toán sắp xếp nổi bọt sắp xếp danh sách bằng cách hoán đổi các phần tử liền kề bao nhiêu lần?

A. Một lần.

B. Hai lần.

C. Mười lần.

D. Nhiều lần.

Câu 3: Trong thuật toán sắp xếp nổi bọt, ta thực hiện hoán đổi giá trị các phần tử liền kề khi nào?

A. Giá trị của chúng tăng.

B. Giá trị của chúng giảm.

C. Giá trị của chúng không đúng thứ tự.

D. Giá trị của chúng không bằng nhau.

Câu 4: 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ì?

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

B. Dãy chưa được sắp xếp tăng dần.

C. Dãy chưa được sắp xếp giảm dần.

Câu 5: Cho dãy số: 6, 4, 5, 3. Nếu sử dụng thuật toán sắp xếp nổi bọt để sắp xếp dãy tăng dần thì sau bao nhiêu vòng lặp thì thuật toán kết thúc?

A. 2 

B. 3

C. 4

D. 5

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

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

Vận dụng kiến thức, GV yêu cầu HS trả lời câu hỏi:

Câu 1: Em hãy lấy ví dụ một bài toán tìm kiếm trong thực tế mà có thể thực hiện bằng thuật toán tìm kiếm nhị phân? Hãy thực hiện thuật toán tìm kiếm nhị phân để giải quyết bài toán đó.