Câu hỏi:

30/05/2022 482

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.

Gói VIP thi online tại VietJack (chỉ 200k/1 năm học), luyện tập hơn 1 triệu câu hỏi có đáp án chi tiết.

Nâng cấp VIP Thi Thử Ngay

Quảng cáo

Trả lời:

verified
Giải bởi Vietjack

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.

Quảng cáo

book vietjack

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Câu 1:

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

Xem đáp án » 30/05/2022 888

Câu 2:

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

Xem đáp án » 30/05/2022 709

Câu 3:

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.

Xem đáp án » 30/05/2022 477

Câu 4:

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.

Media VietJack

Xem đáp án » 30/05/2022 437

Câu 5:

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.

Xem đáp án » 30/05/2022 390

Câu 6:

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

Media VietJack

 

Xem đáp án » 30/05/2022 289

Bình luận


Bình luận