Hãy trình bày thuật toán sắp xếp chọn theo phương pháp làm mịn dần
Câu 26.6 trang 79 SBT Tin học 11: Hãy trình bày thuật toán sắp xếp chọn theo phương pháp làm mịn dần.
Một cách trình bày theo phương pháp làm mịn dần có thể như sau:
Bài toán: Cho trước dãy A có n phần tử. Cần sắp xếp dãy A theo thứ tự tăng dần theo thuật toán chọn.
Bước 1. Phân tích và ý tưởng thiết kế ban đầu.
Ý tưởng ban đầu của thuật toán này như sau:
Với mỗi phần tử của dãy, cần thiết lập vị trí chính xác của vị trí này trong dãy sao cho phía bên trái vị trí này bao gồm các phần tử đã đứng đúng vị trí.
Để thực hiện được ý tưởng trên, cách làm ban đầu là chọn ra phần tử đúng đó và đổi chỗ cho phần tử tại vị trí hiện thời. Từ đó dẫn đến việc phân rã bài
toán như sau:
1 Duyệt chỉ số i từ đầu đến vị trí gần cuối.
2 Tìm phần tử bé nhất trong dãy các phần tử bên phải và
đổi chỗ với phần tử hiện thời.
Bước 2. Chi tiết hoá dòng 1 trong thiết kế trên.
for i in range(n-1):
Bước 3. Chi tiết hoá công việc tại dòng 2.
Để tìm được phần tử nhỏ nhất bên phải vị trí i và sau đó đổi chỗ cho vị trí i chúng ra sẽ tìm vị trí đó thông qua chỉ số. Kết quả của bước này như sau:
Xem thêm các bài giải SBT Tin học 11 Kết nối tri thức hay, chi tiết khác: