Luyện tập tự luận SVIP

Hướng dẫn giải:

- Nguyên lý hoạt động: Thuật toán sắp xếp nổi bọt thực hiện việc so sánh và đổi chỗ các cặp phần tử liền kề nếu chúng đứng sai thứ tự (ví dụ: số đứng trước lớn hơn số đứng sau khi sắp xếp tăng dần). Sau mỗi vòng lặp, phần tử lớn nhất (nếu sắp xếp tăng dần) sẽ được đưa về cuối dãy chưa được sắp xếp. Quá trình lặp được thực hiện cho đến khi không còn cặp phần tử nào cần đổi chỗ.

- Ví dụ minh họa (sắp xếp tăng dần): Dãy ban đầu: 5, 4, 3.

Vòng lặp 1:

So sánh 3 và 4 → đổi chỗ → 5, 3, 4.

So sánh 3 và 5 → đổi chỗ → 3, 5, 4.

Kết thúc vòng 1: số nhỏ nhất (số 3) đã đúng vị trí đầu dãy.

Vòng lặp 2:

So sánh 4 và 5 → đổi chỗ → 3, 4, 5.

Kết thúc vòng 2: số nhỏ thứ 2 (số 4) đã đúng vị trí thứ 2 trong dãy.

Dãy đã được sắp xếp: 3, 4, 5.

Hướng dẫn giải:

- Nguyên lý hoạt động: Thuật toán sắp xếp chọn thực hiện lặp lại việc tìm phần tử nhỏ nhất trong phần dãy chưa được sắp xếp, sau đó đổi chỗ phần tử đó với phần tử ở đầu dãy chưa sắp xếp. Sau mỗi lần chọn, phần tử nhỏ nhất sẽ được đưa về đúng vị trí. Dãy được chia làm hai phần: phần đã sắp xếp (bên trái) và phần chưa sắp xếp (bên phải). Quá trình tiếp tục cho đến khi toàn bộ dãy được sắp xếp.

- Ví dụ minh họa (sắp xếp tăng dần): Dãy ban đầu: 8, 3, 5.

Vòng 1: Chọn phần tử nhỏ nhất trong toàn bộ dãy → 3. Đổi chỗ 3 với 8 → Dãy thành: 3, 8, 5.

Vòng 2: Chọn phần tử nhỏ nhất trong dãy còn lại (8, 5) → 5. Đổi chỗ 5 với 8 → Dãy thành: 3, 5, 8 → Dãy đã sắp xếp: 3, 5, 8.

Hướng dẫn giải:

Đầ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.

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

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

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

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

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

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

Hướng dẫn giải:

Đầ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. 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, ta 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, ta 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 tăng dần.

Hướng dẫn giải:

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

+ Nguyên lí hoạt động: So sánh từng cặp phần tử liền kề, nếu sai thứ tự thì đổi chỗ.

+ Đặc điểm chính: Sau mỗi lượt, phần tử lớn nhất (hoặc nhỏ nhất) được đưa về cuối (hoặc đầu) của phần dãy chưa sắp xếp.

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

+ Nguyên lí hoạt động: Tìm phần tử nhỏ nhất (hoặc lớn nhất) trong phần dãy chưa sắp xếp và đưa về đúng vị trí.

+ Đặc điểm chính: Sau mỗi lượt, ít nhất một phần tử được đặt đúng chỗ mà không cần đổi chỗ nhiều lần.

Hướng dẫn giải:

Hai phần tử liền kề được đổi chỗ khi phần tử đứng trước lớn hơn phần tử đứng sau (nếu sắp xếp tăng dần), hoặc phần tử đứng trước nhỏ hơn phần tử đứng sau (nếu sắp xếp giảm dần).