Đề bài
Hàm sau đây trong Python thể hiện một thuật toán sắp xếp:
| 1 | def Sort (A) $:$ |
|---|---|
| 2 | $n = {\rm{len}}\left( A \right)$ |
| 3 | for $i$ in range $\left( {1,n} \right):$ |
| 4 | value $ = $ A $\left[ i \right]$ |
| 5 | $j = i - 1$ |
| 6 | while $j > = 0$ and $A\left[ j \right] > $ value : |
| 7 | $A\left[ {j + 1} \right] = A\left[ j \right]$ |
| 8 | $j = j - 1$ |
| 9 | $A\left[ {j + 1} \right] = $ value |
Một số bạn học sinh đưa ra các nhận xét về hàm trên như sau:
1. Hàm thể hiện thuật toán sắp xếp chèn (Insertion Sort).
2. Có thể lưu hàm này trong một tệp .py và sử dụng như một thư viện.
3. Với bộ dữ liệu A=[9,7,10,2,3,14], ở lần lặp đầu tiên (i=1), kết quả thực hiện câu lệnh lặp while là A=[7,9,10,2,3,14].
4. Để sắp xếp dãy A theo thứ tự giảm dần cần sửa đổi dòng lệnh 7 và 8 .
Đáp án đúng: 1Đ, 2Đ, 3Đ, 4S
Xem lời giải
Lời giải chi tiết
Để giải quyết bài tập này, ta cần phân tích từng mệnh đề mà học sinh đã nhận xét về hàm Sort:
- Hàm thể hiện thuật toán sắp xếp chèn (Insertion Sort).
Đúng. Đoạn mã này chuyển vị các phần tử lớn hơn giá trị đang xét (value) sang bên phải để tạo khoang chèn giá trị vào vị trí đúng. Đặc trưng này thuộc về thuật toán sắp xếp chèn. - Có thể lưu hàm này trong một tệp .py và sử dụng như một thư viện.
Đúng. File .py là một tệp mã nguồn Python và có thể được nhập vào các chương trình khác dưới dạng module hoặc thư viện. - Với bộ dữ liệu A=[9,7,10,2,3,14], ở lần lặp đầu tiên (i=1), kết quả thực hiện câu lệnh lặp while là A=[7,9,10,2,3,14].
Đúng. Khii=1, cần chèn 7 vào dãy đã sắp xếp [9], ta so sánh 9 và 7, 9 lớn hơn 7, nên đổi chỗ sau đó dừng vòng lặpwhilevà mảng chuyển thành [7,9,10,2,3,14]. - Để sắp xếp dãy A theo thứ tự giảm dần cần sửa đổi dòng lệnh 7 và 8.
Sai. Để sửa đổi thuật toán sắp xếp theo thứ tự giảm dần chỉ cần thay điều kiệnA[j] > valuethànhA[j] < valueở dòng 6, không cần thay đổi dòng lệnh 7 và 8.
Chú ý khi giải
- Khi thực hiện sắp xếp, cần chú ý đến điều kiện trong vòng lặp while vì nó quyết định cách sắp xếp (tăng dần hay giảm dần).
- Đối với bài tập về thuật toán, nên kiểm tra từng bước trên giấy để đảm bảo hiểu rõ cách thức và thứ tự thực hiện của các bước trong thuật toán.
- Sử dụng kỹ thuật gỡ lỗi bằng cách in dòng lệnh và giá trị trung gian có thể giúp xác định nguyên nhân khi chương trình không chạy như ý muốn.