Bài tập Thuật toán sắp xếp có đáp án

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.

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.

Đáp án: A

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

Hình 1: Số nhỏ nhất sắp xếp tại vị trí đầu tiên

Hình 2: Chữ nhỏ nhất chưa được sắp xếp ở vị trí đầu tiên

Hình 3: Dãy thứ tự đã được sắp xếp

Bước 1. Chọn vị trí đầu tiên của dãy (vị trí 1) là vị trí nhỏ nhất.

Bước 2. So sánh với Min số thứ 2, 3, 4, 5. Tìm Min nhỏ nhất và đổi chỗ với vị trí 1, không có thì giữ nguyên vị trí. Thực hiện vòng lặp cho đến khi dãy được sắp xếp.

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