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

Giải SBT Tin học 11 Bài 26: Phương pháp làm mịn dần trong thiết kế chương trình

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.

Lời giải:

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: