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

Tin học lớp 7 bài 14: Thuật toán sắp xếp
Khởi động SGK Tin học 7 bài 14
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:
Bước 1. So sánh số ở vị trí số 1 với vị trí số 2 (19 >16). Nên ta đổi chỗ số 16 và
số 19. Dãy số sau khi sắp xếp: 16, 19, 18, 15.
Bước 2. So sánh số ở vị trí số 2 với vị trí số 3 (19 >18). Nên ta đổi chỗ số 18 và
số 19. Dãy số sau khi sắp xếp: 16, 18, 19, 15.
Bước 3. So sánh số ở vị trí số 3 với vị trí số 4 (19 >15). Nên ta đổi chỗ số 15 và
số 19. Dãy số sau khi sắp xếp: 16, 18, 15, 19.
Bước 4. So sánh số ở vị trí số 1 với vị trí số 2 (18 >16). Nên ta giữ nguyên vị trí.
Bước 5. So sánh số ở vị trí số 2 với vị trí số 3 (18 >15). Nên ta đổi chỗ số 15 và
số 18. Dãy số sau khi sắp xếp: 16, 15, 18, 19.
Bước 6. So sánh số ở vị trí số 3 với vị trí số 4 (19 >18). Nên ta giữ nguyên vị trí.
Bước 7. So sánh số ở vị trí số 1 với vị trí số 2 (16 >15). Nên ta đổi chỗ số 15 và
số 16. Dãy số sau khi sắp xếp: 15, 16, 18, 19.
Dãy số đã được sắp xếp theo vị trí tăng dần. Kết thúc quá trình sắp xếp.
Khám phá SGK Tin học 7 bài 14 Khám phá 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. Trả lời:
Hình 1: Vòng lặp thứ nhất của thuật toán sắp xếp nổi bọt - Lần lặp thứ nhất: 
Bước 1. So sánh chữ thứ nhất với chữ thứ hai. Vì m > h, sai thứ tự ta đổi chỗ vị trí m và h. 
Bước 2. So sánh chữ thứ hai với chữ thứ ba. Vì m > e, sai thứ tự ta đổi chỗ vị trí m và e. 
Bước 3. So sánh chữ thứ ba với chữ thứ tư. Vì m > c, sai thứ tự ta đổi chỗ vị trí m và c. 
Bước 4. So sánh chữ thứ tư với chữ thứ năm. Vì m > a, sai thứ tự ta đổi
chỗ vị trí m và a. Kết thúc lần lặp thứ 1. - Lần lặp thứ hai:
Hình 2: Vòng lặp 2 của thuật toán sắp xếp nổi bọt
Bước 1. So sánh chữ thứ nhất với chữ thứ hai. Vì h > e, sai thứ tự ta đổi chỗ vị trí h và e.
Bước 2. So sánh chữ thứ hai với chữ thứ ba. Vì h > c, sai thứ tự ta đổi chỗ vị trí h và c.
Bước 3. So sánh chữ thứ ba với chữ thứ tư. Vì h > a, sai thứ tự ta đổi chỗ vị trí h và a.
Bước 4. So sánh chữ thứ tư với chữ thứ năm. Vì h < m, giữ nguyên vị trí. Kết thúc lần lặp thứ 2. - Lần lặp thứ 3:
Hình 3: Lần lặp thứ ba của thuật toán sắp xếp nổi bọt 
Bước 1. So sánh chữ thứ nhất với chữ thứ hai. Vì e > c, sai thứ tự ta đổi chỗ vị trí c và e. 
Bước 2. So sánh chữ thứ hai với chữ thứ ba. Vì e > a, sai thứ tự ta đổi chỗ vị trí a và e. 
Bước 3. So sánh chữ thứ ba với chữ thứ tư. Vì e < h, giữ nguyên vị trí. 
Bước 4. So sánh chữ thứ tư với chữ thứ năm. Vì h < m, giữ nguyên vị trí.
Kết thúc lần lặp thứ 3. - Lần lặp thứ 4:
Hình 4: Dãy thẻ đã được sắp xếp xong 
Bước 1. So sánh chữ thứ nhất với chữ thứ hai. Vì c > a, sai thứ tự ta đổi chỗ vị trí c và a. 
Bước 2. So sánh chữ thứ hai với chữ thứ ba. Vì e > c, giữ nguyên. 
Bước 3. So sánh chữ thứ ba với chữ thứ tư. Vì h > e, giữ nguyên. 
Bước 4. So sánh chữ thứ tư với chữ thứ năm. Vì m > h, giữ nguyên. Kết
thúc vòng lặp thứ 4. Dãy đã được sắp xếp xong. Khám phá 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: A
Luyện tập SGK Tin học 7 bài 14 Luyện tập 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. Trả lời: a) Dãy số tăng dần:
- Thuật toán nổi bọt: Vòng lặp 1: 
Bước 1. So sánh số 9 và 6 (9 > 6). Nên đổi chỗ vị trí số 9 và số 6, dãy số
sau khi đổi vị trí: 6, 9, 11, 3, 7. 
Bước 2. So sánh số 9 và 11 (11 > 9). Nên giữ nguyên. 
Bước 3. So sánh số 11 và 3 (11 > 3). Nên đổi chỗ vị trí số 11 và số 3, dãy
số sau khi đổi vị trí: 6, 9, 3, 11, 7. 
Bước 4. So sánh số 11 và 7 (11 > 7). Nên đổi chỗ vị trí số 11 và số 7, dãy
số sau khi đổi vị trí: 6, 9, 3, 7, 11. Vòng lặp 2: 
Bước 5. So sánh số 6 và 9 (9 > 6). Giữ nguyên vị trí, dãy số hiện có 6, 9, 3, 7, 11. 
Bước 6. So sánh số 9 và 3 (9 > 3). Nên đổi chỗ vị trí số 9 và số 3, dãy số
sau khi đổi vị trí: 6, 3, 9, 7, 11. 
Bước 7. So sánh số 9 và 7 (9 > 7). Nên đổi chỗ vị trí số 9 và số 7, dãy số
sau khi đổi vị trí: 6, 3, 7, 9, 11. 
Bước 8. So sánh số 9 và 11 (11 > 9). Giữ nguyên vị trí, dãy số hiện có 6, 3, 7, 9, 11. Vòng lặp 3: 
Bước 9. So sánh số 6 và 3 (6 > 3). Nên đổi chỗ vị trí số 6 và số 3, dãy số
sau khi đổi vị trí: 3, 6, 7, 9, 11. Ta thấy dãy số đã được sắp xếp đúng theo
thứ tự tăng dần, nên kết thúc thuật toán.
⇒ Có 3 vòng lặp được thực hiện khi sắp xếp.
- Thuật toán sắp xếp chọn: 
Bước 1. Chọn số 9 so sánh với những số trong dãy, thấy số 3 là số nhỏ
nhất nên đổi chỗ số 9 và số 3. Dãy số sau khi đổi vị trí: 3, 6, 11, 9, 7. 
Bước 2. Chọn số 6 so sánh với những số trong dãy, thấy số 6 là số nhỏ
nhất và sắp xếp đúng vị trí nên ta giữ nguyên. Dãy số ta được: 3, 6, 11, 9, 7. 
Bước 3. Chọn số 11 so sánh với những số trong dãy, thấy số 7 là số nhỏ
nhất nên đổi chỗ số 11 và số 7. Dãy số sau khi đổi vị trí: 3, 6, 7, 9, 11. 
Bước 4. Chọn số 9 so sánh với những số trong dãy, thấy số 9 là số nhỏ
nhất và sắp xếp đúng vị trí nên ta giữ nguyên. Dãy số ta được: 3, 6, 7, 9, 11.
Ta kiểm tra thấy dãy số đã được sắp xếp theo thứ tự tăng dần. Kết thúc thuật toán.
Thực hiện 4 vòng lặp là có thể sắp xếp số theo đúng vị trí.
b) Dãy chữ cái: H, D, A, B, Y.
- Sắp xếp nổi bọt: (Theo bảng chữ cái). Vòng lặp 1: 
Bước 1. So sánh chữ H và D (H > D). Nên đổi chỗ vị trí chữ H và chữ D,
dãy chữ cái sau khi đổi vị trí: D, H, A, B, Y. 
Bước 2. So sánh chữ H và A (H > A). Nên đổi chỗ vị trí chữ H và chữ A,
dãy chữ cái sau khi đổi vị trí: D, A, H, B, Y. 
Bước 3. So sánh chữ H và B ( H > B). Nên đổi chỗ vị trí chữ H và chữ B,
dãy chữ cái sau khi đổi vị trí: D, A, B, H, Y. 
Bước 4. So sánh chữ H và Y ( Y > H). Nên giữ nguyên vị trí, dãy chữ cái: D, A, B, H, Y. Vòng lặp 2: 
Bước 5. So sánh chữ D và A (D > A). Nên đổi chỗ vị trí chữ D và chữ B,
dãy chữ cái sau khi đổi vị trí: A, D, B, H, Y. 
Bước 6. So sánh chữ D và B (D > B). Nên đổi chỗ vị trí chữ D và chữ B,
dãy chữ cái sau khi đổi vị trí: A, B, D, H, Y. 
Bước 7. So sánh chữ D và H (H > D). Nên giữ nguyên vị trí, dãy chữ cái sắp xếp: A, B, D, H, Y. 
Bước 8. So sánh chữ H và Y (H < Y). Nên giữ nguyên vị trí, dãy chữ cái
sắp xếp: A, B, D, H, Y. Ta thấy dãy chữ cái đã được sắp xếp theo thứ tự. Kết thúc thuật toán.
Sử dụng 2 vòng lặp khi thực hiện bài toán tìm kiếm nổi bọt. - Sắp xếp chọn: 
Bước 1. Chọn chữ H so sánh với những chữ khác trong dãy, thấy chữ A
là chữ nhỏ nhất nên đổi chỗ chữ H và chữ A. Dãy chữ sau khi đổi vị trí: A, D, H, B, Y. 
Bước 2. Chọn chữ D so sánh với những chữ khác trong dãy, thấy chữ B là
chữ nhỏ nhất nên đổi chỗ chữ D và chữ B. Dãy chữ sau khi đổi vị trí: A, B, H, D, Y. 
Bước 3. Chọn chữ H so sánh với những chữ khác trong dãy, thấy chữ D
là chữ nhỏ nhất nên đổi chỗ chữ H và chữ D. Dãy chữ sau khi đổi vị trí: A,
B, D, H, Y. Khi đó ta thấy dãy chữ cái đã được sắp xếp theo đúng thứ tự. Kết thúc thuật toán.
⇒ Sau 3 vòng lặp thực hiện xong bài toán tìm kiếm sắp xếp chọn, Luyện tập 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: C
Vận dụng SGK Tin học 7 bài 14
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ổ Họ và tên Chiều cao Hồ Quang Minh 167 cm Lê Quang Minh 169 cm Nguyễn Minh Huy 168 cm Lê Thị Thảo 160 cm Hồ Như Đăng 155 cm Lê Bích Đào 166 cm
Sắp xếp theo thứ tự không giảm: Sử dụng thuật toán sắp xếp chọn. Trả lời:
Bước 1. Chọn chiều cao của bạn Hồ Quang Minh và so sánh với những bạn còn
lại, ta thấy chiều cao của bạn Hồ Như Đăng nhỏ nhất, ta đổi chỗ bạn Hồ Như
Đăng với bạn Hồ Quang Minh. Chiều cao sắp xếp theo thứ tự: Hồ Như Đăng,
Lê Quang Minh, Nguyễn Minh Huy, Lê Thị Thảo, Hồ Quang Minh, Lê Bích Đào.
Bước 2. Chọn chiều cao của bạn Lê Quang Minh và so sánh với những bạn còn
lại, ta thấy chiều cao của bạn Lê Thị Thảo nhỏ nhất, ta đổi chỗ bạn Lê Quang
Minh với bạn Lê Thị Thảo. Chiều cao sắp xếp theo thứ tự: Hồ Như Đăng, Lê
Thị Thảo, Nguyễn Minh Huy, Lê Quang Minh, Hồ Quang Minh, Lê Bích Đào.
Bước 3. Chọn chiều cao của bạn Nguyễn Minh Huy và so sánh với những bạn
còn lại, ta thấy chiều cao của bạn Lê Bích Đào nhỏ nhất, ta đổi chỗ bạn Nguyễn
Minh Huy với bạn Lê Bích Đào. Chiều cao sắp xếp theo thứ tự: Hồ Như Đăng,
Lê Thị Thảo, Lê Bích Đào, Lê Quang Minh, Hồ Quang Minh, Nguyễn Minh Huy.
Bước 4. Lặp lại vòng lặp. Chọn chiều cao của bạn Lê Quang Minh và so sánh
với những bạn còn lại, ta thấy chiều cao của bạn Hồ Quang Minh nhỏ nhất, ta
đổi chỗ bạn Lê Quang Minh với bạn Hồ Quang Minh. Chiều cao sắp xếp theo
thứ tự: Hồ Như Đăng, Lê Thị Thảo, Lê Bích Đào, Hồ Quang Minh, Lê Quang Minh, Nguyễn Minh Huy.
Bước 4. Chọn chiều cao của bạn Lê Quang Minh và so sánh với những bạn còn
lại, ta thấy chiều cao của bạn Nguyễn Minh Huy nhỏ nhất, ta đổi chỗ bạn Lê
Quang Minh với bạn Nguyễn Minh Huy. Chiều cao sắp xếp theo thứ tự: Hồ
Như Đăng, Lê Thị Thảo, Lê Bích Đào, Hồ Quang Minh, Nguyễn Minh Huy, Lê
Quang Minh. Khi đó ta thấy chiều cao đã được sắp xếp theo thứ tự. Kết thúc thuật toán.
Bảng kết quả sau khi sắp xếp: Họ và tên Chiều cao Hồ Như Đăng 155 cm Lê Thị Thảo 160 cm Lê Bích Đào 166 cm Hồ Quang Minh 167 cm Nguyễn Minh Huy 168 cm Lê Quang Minh 169 cm