Đề bài
Hàm sau đây trong Python thể hiện một thuật toán sắp xếp:
| 1 | ${\rm{defSort}}\left( A \right):$ |
|---|---|
| 2 | $n = {\rm{len}}\left( A \right)$ |
| 3 | for i in range $\left( {n - 1} \right):$ |
| 4 | for $j$ in $range\left( {n - i - 1} \right):$ |
| 5 | if $A\left[ i \right] > A\left[ j \right]:$ |
| 6 | $A\left[ i \right],A\left[ j \right] = A\left[ j \right],A\left[ i \right]$ |
Một số bạn học sinh đưa ra các nhận xét về thuật toán trên như sau:
Lời giải chi tiết
Chúng ta sẽ phân tích từng nhận xét để xem nhận xét nào đúng và nhận xét nào sai:
-
Thuật toán sử dụng mảng A để lưu trữ các phần tử cần sắp xếp.
Nhận xét này đúng vì trong đoạn mã, mảng
Ađược sử dụng để lưu trữ các phần tử cần sắp xếp. -
Đây là thuật toán sắp xếp nổi bọt (Bubble Sort).
Nhận xét này sai. Mã này có vẻ như cố gắng mô phỏng thuật toán sắp xếp nổi bọt nhưng lại mắc lỗi. Cụ thể, điều kiện trong dòng 5 là
A[i] > A[j]nhưng thực tế nên làA[j] > A[j+1]để hoán đổi khi phần tử đứng trước lớn hơn phần tử đứng sau. Ngoài ra, thứ tự hoán đổi các vòng lặp cũng phải sửa. Vậy nên, đây không phải là thuật toán Bubble Sort. -
Nếu điều kiện \( A[i] > A[j] \) đổi thành \( A[i] < A[j] \) thì thuật toán thực hiện sắp xếp giảm dần các phần tử của mảng A.
Nhận xét này sai trong ngữ cảnh của mã lỗi. Điều kiện này thuộc về thuật toán sắp xếp và việc thay đổi điều kiện thực chất chỉ thay đổi cách sắp xếp (từ tăng dần thành giảm dần) khi thuật toán ban đầu đúng, nhưng do lỗi của thuật toán, tình trạng này không đúng trong trường hợp thực tại.
-
Độ phức tạp của thuật toán là \( O(n) \).
Nhận xét này sai. Độ phức tạp của thuật toán Bubble Sort đúng phải là \( O(n^2) \) do có hai vòng lặp lồng nhau mà mỗi vòng lặp thực hiện \( n-i \) lần so sánh và hoán đổi.
Chú ý khi giải
bài tập:
- Hiểu rõ thuật toán cần mô phỏng thông qua mã, nhận xét sai khác giữa mã viết và thuật toán lý thuyết đã học.
- Xem xét kỹ cấu trúc vòng lặp và điều kiện logic để đảm bảo thuật toán thực hiện theo đúng ý tưởng mô phòng.
- Độ phức tạp của thuật toán được xác định bởi số lần lặp lồng nhau, vì vậy chú ý đến cấu trúc lặp của mã.
- Hãy thử tưởng tượng, nếu mã không thực thi như kỳ vọng, hãy kiểm tra các dòng có khả năng thực hiện sai và so sánh với cấu trúc tương ứng mà bạn đã học.