Bài 14. Thuật toán sắp xếp

Bài 14 thuật toán sắp xếp trang 76 sách giáo khoa tin học lớp 7, NXB Chân trời sáng tạo, mời các em tham khảo cùng Bumbii.

Chủ đề 5. Giải quyết vấn đề với sự trợ giúp của máy tính. Bài 14. Thuật toán sắp xếp.

Bài thuật toán sắp xếp nổi bọt

Câu 1

Em hãy sắp xếp dãy chữ cái ở Hình 5 theo thứ tự tăng dần bằng thuật toán sắp xếp nổi bọt (mô phỏng quá trình thực hiện bằng hình vẽ tương tự như các Hình 2, 3, 4). Quy ước, trong bảng chữ cái, chữ đứng trước “nhỏ hơn” chữ đứng sau.

Đáp án:

Vòng lặp 1 thuật toán sắp xếp dãy chữ cái

So sánh chữ cái thứ năm với chữ cái thứ tư. Vì a < c, sai thứ tự, ta đổi chỗ 2 thẻ (thẻ ghi chữ a về vị trí thứ tư).
So sánh chữ cái thứ tư với chữ cái thứ ba. Vì a < e, sai thứ tự, ta đổi chỗ 2 thẻ (thẻ ghi chữ a về vị trí thứ ba).
So sánh chữ cái thứ ba với chữ cái thứ hai. Vì a < h, sai thứ tự, ta đổi chỗ 2 thẻ (thẻ ghi chữ a về vị trí thứ hai).
So sánh chữ cái thứ hai với chữ cái thứ nhất. Vì a < m, sai thứ tự, ta đổi chỗ 2 thẻ (thẻ ghi chữ a về vị trí thứ nhất).
Kết thúc vòng lặp 1, chữ cái a là chữ cái nhỏ nhất đã đúng thứ tự là vị trí thứ nhất trong dãy.

Vòng lặp 2 dãy chữ cái theo thuật toán sắp xếp nổi bọt.

So sánh chữ cái thứ năm với chữ cái thứ tư. Vì c < e, sai thứ tự, ta đổi chỗ 2 thẻ (thẻ ghi chữ c về vị trí thứ tư).
So sánh chữ cái thứ tư với chữ cái thứ ba. Vì c < h, sai thứ tự, ta đổi chỗ 2 thẻ (thẻ ghi chữ c về vị trí thứ ba).
So sánh chữ cái thứ ba với chữ cái thứ hai. Vì c < m, sai thứ tự, ta đổi chỗ 2 thẻ (thẻ ghi chữ c về vị trí thứ hai).
Kết thúc vòng lặp 2, chữ cái c là chữ cái nhỏ thứ hai đã đúng thứ tự là vị trí thứ hai trong dãy.

Vòng lặp 3 dãy chữ cái theo thuật toán sắp xếp nổi bọt.

So sánh chữ cái thứ năm với chữ cái thứ tư. Vì e < h, sai thứ tự, ta đổi chỗ 2 thẻ (thẻ ghi chữ e về vị trí thứ tư).
So sánh chữ cái thứ tư với chữ cái thứ ba. Vì e < m, sai thứ tự, ta đổi chỗ 2 thẻ (thẻ ghi chữ e về vị trí thứ ba).
Kết thúc vòng lặp 3, chữ cái e là chữ cái nhỏ thứ ba đã đúng thứ tự là vị trí thứ ba trong dãy.

Vòng lặp 4 dãy chữ cái theo thuật toán sắp xếp nổi bọt.

So sánh chữ cái thứ năm với chữ cái thứ tư. Vì h < m, sai thứ tự, ta đổi chỗ 2 thẻ (thẻ ghi chữ h về vị trí thứ tư).
Kết thúc vòng lặp 3, chữ cái e là chữ cái nhỏ thứ tư đã đúng thứ tự là vị trí thứ tư trong dãy.
Dãy đã được sắp xếp và thuật toán kết thúc.

Câu 2

Thuật toán sắp xếp nổi bọt thực hiện sắp xếp dãy số không giảm bằng cách nào dưới đây?

A. Đổi chỗ 2 số liền kề nhau nếu chúng đứng sai thứ tự cho đến khi dãy số được sắp xếp.

B. Di chuyển số nhỏ nhất về cuối danh sách.

C. Di chuyển số lớn nhất về đầu danh sách.

Đáp án: Phương án đúng là A.

Phương án B, C sai. Vì thuật toán sắp xếp nổi bọt thực hiện sắp xếp dãy phần tử (tăng dần hay giảm dần) bằng cách thực hiện lặp đi lặp lại việc đổi chỗ 2 phần tử liền kề nếu chúng sai thứ tự.

Bài thuật toán sắp xếp chọn

Câu 1

Em hãy xếp dãy chữ cái ở Hình 5 theo hàng ngang rồi sử dụng thuật toán sắp xếp chọn (mô phỏng quá trình thực hiện bằng hình vẽ như các Hình 7, Hình 8, Hình 9) thực hiện sắp xếp dãy theo thứ tự tăng dần.

Đáp án:

Đầu vào: Dãy thẻ ghi chữ cái xếp từ trái qua phải là m, h, e, c, a.

Đầu ra: Dãy thẻ ghi chữ cái được sắp xếp tăng dần là a, c, e, h, m.

Dãy thẻ chữ cái chưa được sắp xếp.

Số nhỏ nhất chưa ở vị trí đầu tiên nên ta đổi chỗ hai số này

Kết quả sau vòng lặp 1

Số nhỏ nhất chưa ở vị trí đầu tiên nên ta đổi chỗ hai số này

Kết quả sau vòng lặp 2

Số nhỏ nhất đã ở vị trí đầu tiên nên ta không đổi chỗ

Kết quả vòng lặp 3

Số nhỏ nhất đã ở vị trí đầu tiên nên ta không đổi chỗ

Kết quả vòng lặp 4

Sau Vòng lặp 4, dãy chưa sắp xếp còn một chữ cái, đó là chữ cái lớn nhất đã ở đúng vị trí cuối cùng của dãy. Vậy dãy ban đầu đã được sắp xếp và thuật toán kết thúc.

Câu 2

Thuật toán sắp xếp chọn thực hiện sắp xếp dãy số tăng dần bằng cách nào dưới đây?

A. Đổi chỗ 2 số liền kề nhau nếu chúng đứng sai thứ tự cho đến khi dãy số được sắp xếp.

B. Lặp lại quá trình chọn số nhỏ nhất trong dãy chưa sắp xếp và đưa số này về vị trí đầu tiên của dãy đó.

Đáp án: phương án đúng là B.

Phương án A là thuật toán sắp xếp nổi bọt.

LUYỆN TẬP

Câu 1

Liệt kê các vòng lặp của thuật toán sắp xếp nổi bọt, thuật toán sắp xếp chọn để sắp xếp các dãy sau theo thứ tự tăng dần:

a) Dãy số: 9, 6, 11, 3, 7.

b) Dãy chữ cái: H, D, A, B, Y.

Đáp án: bài thuật sắp xếp

Liệt kê các vòng lặp khi sắp xếp tăng dần dãy số 9, 6, 11, 3, 7 theo thuật toán sắp xếp nổi bọt.

Liệt kê các vòng lặp khi sắp xếp tăng dần dãy số 9, 6, 11, 3, 7 theo thuật toán sắp xếp chọn.

Liệt kê các vòng lặp khi sắp xếp tăng dần dãy số H, D, A, B, Y theo thuật toán sắp xếp nổi bọt.

Liệt kê các vòng lặp khi sắp xếp tăng dần dãy số H, D, A, B, Y theo thuật toán sắp xếp chọn.

Câu 2

Chỉ ra phương án sai. Ý nghĩa của việc chia bài toán thành bài toán nhỏ hơn là:

A. Giúp công việc đơn giản hơn.

B. Giúp công việc dễ giải quyết hơn.

C. Làm cho công việc trở nên phức tạp hơn.

D. Giúp bài toán trở nên dễ hiểu hơn.

Đáp án: Phương án sai là C.

Ý nghĩa của việc chia bài toán thành bài toán nhỏ hơn là:

Giúp công việc đơn giản hơn

Giúp công việc dễ giải quyết hơn.

Giúp bài toán trở nên dễ hiểu hơn.

VẬN DỤNG

Sử dụng một thuật toán đã học để thực hiện sắp xếp các bạn trong tổ em theo thứ tự chiều cao không giảm (ghi chiều cao của các bạn theo cùng đơn vị đo là cm vào bảng theo mẫu Bảng 1 dưới đây).

Bảng 1. Chiều cao của các bạn trong tổ