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

Với giải Câu 26.6 trang 79 SBT Tin học 11 Kết nối tri thức chi tiết trong Bài 26: Phương pháp làm mịn dần trong thiết kế chương trình giúp học sinh dễ dàng xem và so sánh lời giải, từ đó biết cách làm bài tập Tin học 11. Mời các bạn đón xem:

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.

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:

SBT Tin học 11 (Kết nối tri thức) Bài 26: Phương pháp làm mịn dần trong thiết kế chương trình (ảnh 1)