Kết quả cuối giống nhau, các bước có thể khác
Ba thuật toán có thể cùng biến dãy thành tăng dần nhưng chọn và đổi phần tử theo cách khác nhau. Khi đề hỏi sau một lượt, phải biết chính xác thuật toán và chiều duyệt.
Ba ý tưởng
Sắp xếp chọn: tìm phần tử nhỏ nhất trong phần chưa xếp rồi đưa về đầu phần đó. Sắp xếp chèn: lấy phần tử kế tiếp, dịch các phần tử lớn hơn trong phần đầu đã xếp để chèn vào đúng chỗ. Nổi bọt: so các cặp kề, đổi chỗ khi sai thứ tự; trong phiên bản duyệt trái sang phải, phần tử lớn nhất của đoạn được đẩy về cuối sau một lượt.
Bài này sắp tăng không giảm. Các phiên bản duyệt ngược hoặc chọn phần tử lớn nhất có bước trung gian khác; cần bám mã được cho.
Theo dõi sắp xếp chèn
Dãy [6,2,5,1]:
| Sau khi chèn | Dãy |
|---|---|
| 2 vào phần đầu [6] | [2,6,5,1] |
| 5 vào phần đầu [2,6] | [2,5,6,1] |
| 1 vào phần đầu [2,5,6] | [1,2,5,6] |
Mỗi lượt chỉ bảo đảm phần đầu đã xét được sắp; phần sau có thể còn chưa đúng thứ tự.
Thử vận dụng
Sắp xếp chọn phần tử nhỏ nhất, lượt đầu trên [6,2,5,1] cho dãy nào?
Đây phù hợp lượt chèn 2, không phải lượt chọn nhỏ nhất toàn dãy.
Đúng: đổi 1 với phần tử đầu 6.
Chưa đưa phần tử nhỏ nhất về đầu.
Đây là kết quả một lượt nổi bọt trái sang phải.
Lời giải
Nhỏ nhất là 1 ở cuối; đổi chỗ với 6 ở đầu, được [1,2,5,6]. Dãy tình cờ đã xếp xong sau lượt này.
Mã sắp xếp chèn
```python
a = [6, 2, 5, 1]
for i in range(1, len(a)):
value = a[i]
j = i - 1
while j >= 0 and a[j] > value:
a[j + 1] = a[j]
j -= 1
a[j + 1] = value
print(a)
```
value giữ phần tử cần chèn trong lúc dịch. Điều kiện j >= 0 được xét trước để không đọc vượt phía trái. Kết quả [1,2,5,6].
Ví dụ xem cách làm
Nổi bọt tăng dần, duyệt trái sang phải và đổi mọi cặp kề sai thứ tự: sau một lượt trên [4,1,3,2] là gì?
Lời giải
[1,3,2,4]. Các lần đổi: 4 với 1, 4 với 3, 4 với 2. Chưa được kết luận toàn dãy đã sắp vì 3 còn đứng trước 2.
Ví dụ xem cách làm
Vì sao mã chèn lưu value trước khi dịch các phần tử?
Lời giải
Việc dịch có thể ghi đè vị trí ban đầu a[i]. value giữ giá trị cần chèn để đặt vào ô trống cuối cùng.
Những điều cần nhớ
Chọn: tìm cực trị; chèn: đưa phần tử vào đoạn đầu đã xếp; nổi bọt: đổi cặp kề. Mô phỏng theo đúng chiều và phạm vi vòng lặp của đề.
Đang học