Bài 4. Sắp xếp nổi bọt

Bài Sắp xếp nổi bọt trang 87 SGK Tin Học lớp 7 – Cánh Diều, mời các em tham khảo cùng Bumbii.

Chủ đề F. Giải quyết vấn đề với sự trợ giúp của máy tính. Bài 4. Sắp xếp nổi bọt.

MÔ TẢ THUẬT TOÁN SẮP XẾP NỔI BỌT

Lặp khi (dãy chưa sắp xếp xong = đúng):

a) Thực hiện một số 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

LUYỆN TẬP

Câu hỏi. Hãy mô phỏng thuật toán sắp xếp nổi bọt cho một dãy số nguyên tuỳ chọn, không ít hơn 5 phần tử. Sau bao nhiêu lượt đi từ đầu đến cuối dãy để so sánh và đổi chỗ thì thuật toán kết thúc? Tổng số có bao nhiêu lần đổi chỗ hai phần tử liền kề?

Đáp án:

Ví dụ dãy 5 số: 5, 1, 4, 2, 8.

– Thực hiện 3 lượt để so sánh và đổi chỗ thì thuật toán kết thúc.

– Có 4 lần đổi chỗ hai phần tử liền kề.

VẬN DỤNG

Bài 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 dưới đây đã 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?

Đáp án:

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à dãy chưa có thứ tự mong muốn (dãy đã sắp xếp thứ tự tăng dần).

2) đúng.

Bài 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?

Đáp án:

Nếu viết dãy theo chiều dọc từ trên xuống dưới, mỗi số trong dãy coi như một bọt nước, thì việc đổi chỗ tương đương với bọt nước nhẹ hơn sẽ nổi dần lên, nặng hơn sẽ chìm dần xuống.