Hãy trình bày ý tưởng của thuật toán sắp xếp chọn (Selection Sort). Vận dụng phương pháp làm

Câu hỏi số 977435:

Vận dụng

Hãy trình bày ý tưởng của thuật toán sắp xếp chọn (Selection Sort). Vận dụng phương pháp làm mịn dần (stepwise refinement) để thiết kế chương trình thực hiện thuật toán sắp xếp chọn đối với một dãy số nguyên.

Quảng cáo

Xem lời giải

Câu hỏi:977435

Phương pháp giải

Sử dụng nguyên lý tìm phần tử nhỏ nhất và đưa về đầu dãy chưa sắp xếp.

Giải chi tiết

1. Ý tưởng thuật toán:

- Bước 1: Tìm phần tử nhỏ nhất trong dãy hiện tại.

- Bước 2: Hoán đổi phần tử nhỏ nhất đó với phần tử đầu tiên của dãy chưa sắp xếp.

- Bước 3: Lặp lại quá trình với phần còn lại của dãy cho đến khi toàn bộ dãy được sắp xếp.

2. Làm mịn dần:

- Mức 1: Duyệt qua dãy và thực hiện sắp xếp.

- Mức 2: Dùng vòng lặp i chạy từ đầu đến cuối dãy - 1. Tìm vị trí min trong đoạn từ i đến cuối. Đổi chỗ phần tử tại i với phần tử tại vị trí min.

- Mức 3: Cụ thể hóa bằng mã lệnh với hai vòng lặp lồng nhau.

Thuật toán Sắp xếp chọn:

for i = 0 to n - 2:

min_idx = i

for j = i + 1 to n - 1:

if a[j] < a[min_idx]:

min_idx = j

swap(a[i], a[min_idx])

Group 2K8 ôn Thi ĐGNL & ĐGTD Miễn Phí

Câu hỏi trước Câu tiếp theo

>> 2K9 Chú ý! Lộ Trình Sun 2027 - 1 lộ trình ôn đa kỳ thi (TN THPT, ĐGNL (Hà Nội/ Hồ Chí Minh), ĐGNL Sư Phạm, ĐGTD, ĐGNL Bộ Công an, ĐGNL Bộ Quốc phòng- Click xem ngay) tại Tuyensinh247.com. Cập nhật bám sát bộ SGK mới, Thầy Cô giáo giỏi, 3 bước chi tiết: Nền tảng lớp 12; Luyện thi chuyên sâu; Luyện đề đủ dạng đáp ứng mọi kì thi.