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.
Bằng cách nhấp vào Đăng nhập, bạn đồng ý Chính sách bảo mật và Điều khoản sử dụng của chúng tôi. Nếu đây không phải máy tính của bạn, để đảm bảo an toàn, hãy sử dụng Cửa sổ riêng tư (Tab ẩn danh) để đăng nhập (New Private Window / New Incognito Window).
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:
Tham gia Cộng đồng Lazi trên các mạng xã hội | |
Fanpage: | https://www.fb.com/lazi.vn |
Group: | https://www.fb.com/groups/lazi.vn |
Kênh FB: | https://m.me/j/AbY8WMG2VhCvgIcB |
LaziGo: | https://go.lazi.vn/join/lazigo |
Discord: | https://discord.gg/4vkBe6wJuU |
Youtube: | https://www.youtube.com/@lazi-vn |
Tiktok: | https://www.tiktok.com/@lazi.vn |
Hôm nay bạn thế nào? Hãy nhấp vào một lựa chọn, nếu may mắn bạn sẽ được tặng 50.000 xu từ Lazi
Vui | Buồn | Bình thường |