BÀI 16: THUẬT TOÁN SẮP XẾP (15 CÂU)

I. NHẬN BIẾT (5 CÂU)

Câu 1: Thuật toán sắp xếp nổi bọt là gì?

Trả lời:

Thuật toán sắp xếp nổi bọt là thuật toán sắp xếp được thực hiện bằng cách hoán đổi nhiều lần các phần tử liền kề nếu giá trị của chúng không đúng thứ tự.

Câu 2: Thuật toán sắp xếp chọn là gì?

Trả lời:

Thuật toán sắp xếp chọn xét từng vị trí từ đầu đến cuối dãy, so sánh trực tiếp phần tử ở vị trí được xét với những phần tử ở phía sau nó và hoán đổi nếu chúng chưa đúng thứ tự.

Câu 3: Hãy mô tả thuật toán sắp xếp nổi bọt.

Trả lời:

1. Với vị trí đầu tiên, thực hiện một vòng lặp như sau:

1.1. So sánh hai phần tử đứng cạnh nhau theo thứ tự từ cuối dãy lên vị trí đầu tiên.

1.2. Nếu phần tử đứng sau nhỏ hơn phần tử đứng trước thì đổi chỗ chúng cho nhau.

1.3. Cuối vòng lặp em sẽ nhận được dãy số với phần tử nhỏ nhất nổi lên vị trí đầu tiên.

2. Với vòng lặp thứ hai, em thực hiện một vòng lặp tương tự như trên.

2.1. So sánh hai phần tử đứng cạnh nhau theo thứ tự từ cuối dãy lên vị trí thứ hai.

2.2. Nếu phần tử đứng sau nhỏ hơn phần tử đứng trước thì đổi chỗ chúng cho nhau.

2.3. Cuối vòng lặp em sẽ nhận được dãy số với phần tử nhỏ thứ nhì nổi lên vị trí thứ hai.

3. Tương tự như trên với các vị trí thứ 3, thứ tư,… đến vị trí trước vị trí cuối cùng.
4. Kết thúc, em sẽ nhận được dãy số đã được sắp xếp theo thứ tự từ nhỏ đến lớn.

Câu 4: Hãy mô tả thuật toán sắp xếp chọn.

Trả lời:

1. Với vị trí đầu tiên, thực hiện vòng lặp như sau:

1.1. So sánh từng phần tử (kể từ vị trí thứ hai đến vị trí cuối cùng) với phần tử tại vị trí đầu tiên.

1.2. Nếu phần tử được xét nhỏ hơn phần tử tại vị trí đầu tiên thì hoán đổi nó với phần tử tại vị trí đầu tiên.

1.3. Cuối vòng lặp, em sẽ nhận được dãy số với phần tử nhỏ nhất được đưa về vị trí đầu tiên.

2. Với vị trí thứ hai, thực hiện một vòng lặp tương tự như trên.

2.1. So sánh từng phần tử (kể từ vị trí thứ ba đến vị trí cuối cùng) với phần tử tại vị trí thứ hai.

2.2. Nếu phần tử được xét nhỏ hơn phần tử thứ hai thì hoán đổi nó với phần tử tại vị trí thứ hai.

2.3 Cuối vòng lặp, em sẽ nhận được dãy số với phần tử nhỏ nhì được đưa về vị trí thứ hai.

3. Tương tự như trên với các vị trí thứ ba, thứ tư,… đến vị trí được vị trí cuối cùng.
4. Kết thúc, em sẽ nhận được dãy số đã được sắp xếp theo thứ tự từ nhỏ đến lớn.

Câu 5: Tác dụng của việc chia bài toán thành những bài toán nhỏ hơn là gì?

Trả lời:

Việc chia bài toán thành những bài toán nhỏ hơn giúp thuật toán dễ hiểu và dễ thực hiện hơn.

II. THÔNG HIỂU (4 CÂU)

Câu 1: Em hãy chọn thuật toán sắp xếp hợp lý cho từng trường hợp sau:

1. a) Hoán đổi vị trí hai phần tử liên tiếp khi chúng không đúng thứ tự là thuật toán nào?
2. b) Tìm phần tử nhỏ nhất trong dãy và đổi chỗ phần tử này với phần tử đầu tiên của dãy chưa được sắp xếp là thuật toán nào?

Trả lời:

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

Câu 2: Em hãy nêu sự khác nhau giữa thuật toán sắp xếp nổi bọt và thuật toán sắp xếp chọn?
Trả lời:

Sự khác nhau giữa thuật toán sắp xếp nổi bọt và thuật toán sắp xếp chọn là:

- Cách thức hoạt động :

+ Thuật toán sắp xếp nổi bọt di chuyển lần lượt qua danh sách, so sánh cặp phần tử liền kề và hoán đổi chúng nếu chúng không đúng thứ tự. Quá trình này lặp lại cho đến khi không còn phần tử nào cần phải hoán đổi.

+ Thuật toán sắp xếp chọn lựa chọn phần tử nhỏ nhất từ danh sách và đặt nó ở vị trí đầu tiên. Sau đó, nó chọn phần tử nhỏ nhất thứ hai và đặt nó ở vị trí thứ hai, và tiếp tục như vậy cho đến khi danh sách được sắp xếp hoàn toàn.

- Hiệu suất: Thuật toán sắp xếp nổi bọt thường sẽ hiệu quả hơn thuật toán sắp xếp chọn đối với danh sách nhỏ hoặc đã gần sắp xếp. Tuy nhiên thì cả 2 đều không thể hoạt động tốt với danh sách lớn vì phải thực hiện nhiều lần lặp.

Câu 3: Dùng thuật toán sắp xếp nổi bọt để sắp xếp một dãy số tăng dần. Mỗi vòng lặp sẽ duyệt các phần tử từ cuối danh sách đến đầu danh sách. Kết thúc vòng lặp thứ nhất, phần tử đầu tiên sẽ có giá trị là gì?

Trả lời:

Kết thúc vòng lặp thứ nhất, phần tử đầu tiên sẽ có giá trị nhỏ nhất trong dãy số.

Câu 4: Sau vòng lặp thứ nhất của thuật toán sắp xếp chọn, phương án nào đúng?

1. Phần tử có giá trị nhỏ nhất trong dãy được tìm thấy và đổi chỗ cho phần tử đứng đầu dãy.
2. Phần tử có giá trị lớn nhất trong dãy được tìm thấy và đổi chỗ cho phần tử đứng đầu dãy.
3. Các phần tử liền kề được hoán đổi.
4. Phần tử có giá trị nhỏ nhất sẽ đổi vị trí cho phần tử cuối dãy.

Trả lời:

Đáp án: A. Phần tử có giá trị nhỏ nhất trong dãy được tìm thấy và đổi chỗ cho phần tử đứng đầu dãy.

III, VẬN DỤNG (5 CÂU)

Câu 1: Em hãy liệt kê các bước của thuật toán sắp xếp nổi bọt để sắp xếp các số 3, 2, 4, 1, 5 theo thứ tự tăng dần.

Trả lời:

Câu 2: Em hãy liệt kê các bước của thuật toán sắp xếp chọn để sắp xếp các số 3, 2, 4, 1, 5 theo thứ tự tăng dần.

Trả lời:

Câu 3: Nếu sử dụng thuật toán sắp xếp chọn để sắp xếp dãy số 8, 22, 7, 19, 5 theo thứ tự tăng dần thì số lần thực hiện thao tác hoán đổi giá trị trong vòng lặp thứ nhất là bao nhiêu?

Trả lời:

Đáp án là 2.

Vòng lặp 1:

| 8 | 22 | 7 | 19 | 5 | → lần 1: | 7 | 22 | 8 | 19 | 5 | → lần 2: | 5 | 22 | 7 | 19 | 8 |

Câu 4: Cho dãy số sau: 15, 20, 10, 18.
Em hãy sử dụng thuật toán sắp xếp nổi bọt để sắp xếp dãy số tăng dần. Mỗi vòng lặp sẽ duyệt từ phần tử cuối đến phần tử đầu tiên.

Trả lời:

| 15 | 20 | 10 | 18 | → | 10 | 15 | 20 | 18 | → | 10 | 15 | 18 | 20 |

Câu 5: Em hãy sử dụng thuật toán sắp xếp chọn để sắp xếp bốn thành viên trong gia đình bạn Hải (bao gồm: bố, mẹ, Hải và em gái) (như hình minh họa dưới) theo thứ tự tăng dẫn của chiều cao.

Trả lời:

Vòng lặp thứ nhất: Em gái là người thấp nhất nên đổi chỗ em gái với bố. Thứ tự mới bây giờ là em gái, bố, mẹ, Hải.

Vòng lặp thứ hai: Hải là người thấp nhất trong dãy còn lại nên Hải đổi chỗ với bố. Thứ tự mới bây giờ là em gái, Hải, mẹ, bố.

Vòng lặp thứ ba: Mẹ ở đúng vị trí nên thứ tự sắp xếp đã đúng.

IV. VẬN DỤNG CAO (1 CÂU)

Câu 1: Bài tập thực hành:

Em hãy ghi lại kết quả điểm học tập môn Tin học của các bạn trong tổ. Thực hiện thuật toán sắp xếp chọn hoặc sắp xếp nổi bọt để sắp xếp điểm theo thứ tự giảm dần. Dựa trên kết quả sắp xếp, hãy cho biết danh sách tên các bạn tương ứng theo kết quả sắp xếp đó.

Trả lời:

- Gợi ý cách làm:

- Bảng điểm môn Tin học:

- Thực hiện thuật toán sắp xếp nổi bọt:

- Bảng điểm môn Tin học sau khi sắp xếp: