Giải Tin học 7 Bài 14 (Chân trời sáng tạo): Thuật toán sắp xếp

Giải bài tập Tin học 7 Bài 14: Thuật toán sắp xếp

Video giải bài tập Tin học 7 Bài 14: Thuật toán sắp xếp

Khởi động trang 76 Bài 14 Tin học 7: Có 4 tấm thẻ, mỗi thẻ ghi một số và xếp thành một dãy dọc trên mặt bàn từ trên xuống dưới như Hình 1. Em hãy trao đổi với bạn để chỉ ra cách sắp xếp dãy thẻ theo thứ tự giá trị tăng dần của số ghi trên thẻ, với điều kiện chỉ có thể di chuyển các thẻ bằng cách đổi chỗ các cặp thẻ liền kề.

Trả lời:

Cách sắp xếp: thực hiện lặp đi lặp lại việc đổi chỗ 2 số liền kề trong một dãy số nếu chúng đứng sai thứ tự số sau bé hơn số trước cho đến khi dãy thẻ số được sắp xếp theo thứ tự tăng dần

1. Thuật toán sắp xếp nổi bọt

Khám phá 1 trang 79 Tin học 7: 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

Trả lời:

Mô phỏng thuật toán sắp xếp nổi bọt

Đầu vào: dãy thẻ ghi các chữ cái sắp xếp từ trên xuống dưới là m, h, e, c, a.

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

- Vòng lặp 1:

+ So sánh chữ thứ 5 với chữ thứ 4 a < c sai thứ tự ta tiến hành đổi chỗ thu được dãy m, h, e, a, c

+ So sánh chữ thứ 4 với chữ thứ 3 c < e sai thứ tự ta tiến hành đổi chỗ thu được dãy m, h, a, e, c

+ So sánh chữ thứ 3 với chữ thứ 2 a < h sai thứ tự ta tiến hành đổi chỗ thu được dãy m, a, h, e, c

+ So sánh chữ thứ 2 với chữ thứ 1 a < m sai thứ tự ta tiến hành đổi chỗ thu được dãy a, m, h, e, c

- Vòng lặp 2:

+ So sánh chữ thứ 5 với chữ thứ 4 c < e sai thứ tự ta tiến hành đổi chỗ thu được dãy a, m, h, c, e

+ So sánh chữ thứ 4 với chữ thứ 3 c < h sai thứ tự ta tiến hành đổi chỗ thu được dãy a, m, c, h, e

+ So sánh chữ thứ 3 với chữ thứ 2 c < m sai thứ tự ta tiến hành đổi chỗ thu được dãy a, c, m, h, e

+ So sánh chữ thứ 2 với chữ thứ 1 c > a đúng thứ tự ta tiến hành giữ nguyên thứ tự.

- Vòng lặp 3:

+ So sánh chữ thứ 5 với chữ thứ 4 e < h sai thứ tự ta tiến hành đổi chỗ thu được dãy a, c, m, e, h

+ So sánh chữ thứ 4 với chữ thứ 3 e < m sai thứ tự ta tiến hành đổi chỗ thu được dãy a, c, e, m, h

+ So sánh chữ thứ 3 với chữ thứ 2 e > c đúng thứ tự ta tiến hành giữ nguyên thứ tự.

+ So sánh chữ thứ 2 với chữ thứ 1 c > a đúng thứ tự ta tiến hành giữ nguyên thứ tự.

- Vòng lặp 4:

+ So sánh chữ thứ 5 với chữ thứ 4 h < m sai thứ tự ta tiến hành đổi chỗ thu được dãy a, c, e, h, m

+ So sánh chữ thứ 4 với chữ thứ 3 h > đúng thứ tự ta tiến hành giữ nguyên thứ tự.

+ So sánh chữ thứ 3 với chữ thứ 2 e > c đúng thứ tự ta tiến hành giữ nguyên thứ tự.

+ So sánh chữ thứ 2 với chữ thứ 1 c > a đúng thứ tự ta tiến hành giữ nguyên thứ tự. Kết thúc vòng lặp ta thu được dãy cần sắp xếp là a, c, e, h, m.

Khám phá 2 trang 79 Tin học 7: 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.

Trả lời:

Đáp án: A

Thuật toán sắp xếp nổi bọt thực hiện lặp đi lặp lại việc đổi chỗ 2 số liền kề trong một dãy số nếu chúng đứng sai thứ tự (số sau bé hơn số trước) cho đến khi dãy thẻ số được sắp xếp theo thứ tự tăng dần.

2. Thuật toán sắp xếp chọn

Khám phá 1 trang 82 Tin học 7: 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.

Trả lời:

Mô phỏng thuật toán sắp xếp chọn

Đầu vào: dãy thẻ ghi các chữ cái sắp xếp từ trên xuống dưới là m, h, e, c, a.

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

- Vòng lặp 1:

Tìm chữ cái nhỏ nhất là a chưa ở vị trí đầu tiên nên ta đổi chỗ a và m thu được dãy a, h, e, c, m.

Dãy chưa sắp xếp h, e, c, m.

- Vòng lặp 2:

Chữ cái nhỏ nhất trong dãy chưa sắp xếp là c. c chưa ở vị trí đầu tiên, đổi chỗ c và h thu được dãy a, c, e, h, m.

Dãy chưa sắp xếp e, h, m.

- Vòng lặp 3:

Chữ cái nhỏ nhất trong dãy chưa sắp xếp là e. e đang ở vị trí đầu tiên nên ko cần đổi chỗ.

Dãy chưa sắp xếp h, m.

- Vòng lặp 4:

Chữ cái nhỏ nhất trong dãy chưa sắp xếp là h. h đang ở vị trí đầu tiên nên không cần đổi chỗ.

Dãy chưa sắp xếp m. Vậy dãy đã được sắp xếp là a, c, e, h, m.

Dãy số cuối cùng sau khi được sắp xếp

Khám phá 2 trang 82 Tin học 7: 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 đó.

Trả lời:

Đáp án: B

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 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 đó.

Luyện tập (trang 82)

Luyện tập 1 trang 82 Tin học 7: 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 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.

Trả lời:

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

- Thuật toán sắp xếp nổi bọt:

+ Vòng lặp 1:

9, 6, 11, 3, 7 → 9, 6, 11, 3, 7 → 9, 6, 3, 11, 7 → 9, 3, 6, 11, 7 → 3, 9, 6, 11, 7

+ Vòng lặp 2:

3, 9, 6, 11, 7 → 3, 9, 6, 7, 11 → 3, 9, 6, 7, 11 → 3, 6, 9, 7, 11 → 3, 6, 9, 7, 11

+ Vòng lặp 3:

3, 6, 9, 7, 11 → 3, 6, 9, 7, 11 → 3, 6, 7, 9, 11 → 3, 6, 7, 9, 11 → 3, 6, 7, 9, 11

+ Vòng lặp 4:

3, 6, 7, 9, 11 → 3, 6, 7, 9, 11 → 3, 6, 7, 9, 11 → 3, 6, 7, 9, 11 → 3, 6, 7, 9, 11

- Thuật toán sắp xếp chọn:

+ Vòng lặp 1:

9, 6, 11, 3, 7 → 3, 6, 11, 9, 7

+ Vòng lặp 2:

3, 6, 11, 9, 7 → 3, 6, 11, 9, 7

+ Vòng lặp 3:

3, 6, 11, 9, 7 → 3, 6, 7, 9, 11

+ Vòng lặp 4:

3, 6, 7, 9, 11 → 3, 6, 7, 9, 11

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

- Thuật toán sắp xếp nổi bọt:

+ Vòng lặp 1:

H, D, A, B, Y → H, D, A, B, Y → H, D, A, B, Y → H, A, D, B, Y → A, H, D, B, Y

+ Vòng lặp 2:

A, H, D, B, Y → A, H, D, B, Y → A, H, B, D, Y → A, B, H, D, Y → A, B, H, D, Y

+ Vòng lặp 3:

A, B, H, D, Y → A, B, H, D, Y → A, B, D, H, Y → A, B, D, H, Y → A, B, D, H, Y

+ Vòng lặp 4:

A, B, D, H, Y → A, B, D, H, Y → A, B, D, H, Y → A, B, D, H, Y → A, B, D, H, Y

- Thuật toán sắp xếp chọn

+ Vòng lặp 1: H, D, A, B, Y → A, D, H, B, Y

+ Vòng lặp 2: A, D, H, B, Y → A, B, H, D, Y

+ Vòng lặp 3: A, B, H, D, Y → A, B, D, H, Y

+ Vòng lặp 4: A, B, D, H, Y → A, B, D, H, Y

Luyện tập 2 trang 82 Tin học 7: 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.

Trả lời:

Đáp án: C

Việc chia bài toán thành bài toán nhỏ hơn giúp công việc đơn giản, dễ giải quyết, dễ hiểu hơn.

Vận dụng (trang 82)

Vận dụng trang 82 Tin học 7: 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ổ

Trả lời:

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

Sử dụng thuật toán sắp xếp chọn

- Vòng lặp 1: 153, 147, 161, 156, 159, 160 → 147, 153, 161, 156, 159, 160

- Vòng lặp 2: 147, 153, 161, 156, 159, 160 → 147, 153, 161, 156, 159, 160

- Vòng lặp 3: 147, 153, 161, 156, 159, 160 → 147, 153, 156, 161, 159, 160

- Vòng lặp 3: 147, 153, 156, 161, 159, 160 → 147, 153, 156, 159, 161, 160

- Vòng lặp 4 : 147, 153, 156, 159, 161, 160 → 147, 153, 156, 159, 160, 161

Lý thuyết Tin Học 7 Bài 14: Thuật toán sắp xếp

1. Thuật toán sắp xếp nổi bọt

- 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ự.

- Mô tả thuật toán sắp xếp nổi bọt (áp dụng cho bài toán sắp xếp dãy tổng quát)

Đầu vào: Dãy chưa được sắp xếp.

Đầu ra: Dãy được sắp xếp không giảm.

1. Chuyển phần tử nhỏ nhất về vị trí đầu tiên.

+ So sánh từng phần tử của dãy với phần tử liền trước, lần lượt từ phần tử cuối cùng lên phần tử đầu tiên.

+ Nếu nhỏ hơn thì đổi chỗ hai phần tử.

+ Kết thúc vòng lặp, phần từ nhỏ nhất "nổi lên" vị trí đầu tiên của dãy.

2. Chuyển phần tử nhỏ thứ hai về vị trí thứ hai.

+ So sánh từng phần tử của dãy với phần tử liền trước, lần lượt từ phần tử cuối cùng lên phần tử thứ hai.

+ Nếu nhỏ hơn thì đổi chỗ hai phần tử.

+ Kết thúc vòng, phần tử nhỏ thứ hai "nổi lên" vị trí thứ hai của dãy.

3. Thực hiện tương tự như trên với phần tử nhỏ thứ ba, thứ tư, ... cho đến phần tử liền trước phần tử cuối cùng.

4. Kết thúc thuật toán, ta sẽ nhận được dãy số đã được sắp xếp theo thứ tự tăng dần.

2. Thuật toán sắp xếp chọn

- Thuật toán sắp xếp chọn thực hiện lặp lại quá trình chọn phần tử nhỏ nhất trong dãy chưa sắp xếp và đưa phần tử này về vị trí đầu tiên của dãy đó.

Ví dụ:

Hình 2. Minh họa thuật toán sắp xếp nổi bọt

Xem thêm lời giải bài tập Tin học lớp 7 Chân trời sáng tạo hay, chi tiết khác:

Bài 1: Thiết bị vào và thiết bị ra

Bài 2: Hệ điều hành và phần mềm ứng dụng

Bài 3: Thực hành thao tác với tệp và thư mục

Bài 4: Phân loại tệp và bảo vệ dữ liệu trong máy tính

Bài 5: Mạng xã hội

Xem thêm tài liệu Tin học lớp 7 Chân trời sáng tạo hay, chi tiết khác:

Lý thuyết Bài 14: Thuật toán sắp xếp

Trắc nghiệm Bài 14: Thuật toán sắp xếp