Trong bài viết này, chúng ta sẽ học về Selection sort và triển khai của nó trong Python 3.x hoặc trước đó.
Trong thuật toán selection sort, một mảng được sắp xếp bằng cách đệ quy tìm phần tử nhỏ nhất từ phần chưa sắp xếp và chèn nó vào đầu. Hai mảng con được hình thành trong quá trình thực thi Selection sort trên một mảng cho trước.
- Mảng con đã được sắp xếp.
- Mảng con chưa được sắp xếp.
Trong mỗi lần lặp của selection sort, phần tử nhỏ nhất từ mảng con chưa sắp xếp được lấy ra và chèn vào mảng con đã sắp xếp.
Hãy xem biểu diễn trực quan của thuật toán:
Bây giờ hãy xem triển khai thuật toán:
Ví dụ
A = ['t', 'u', 't', 'o', 'r', 'i', 'a', 'l']
for i in range(len(A)):
min_ = i
for j in range(i+1, len(A)):
if A[min_] > A[j]:
min_ = j
# swap
A[i], A[min_] = A[min_], A[i]
# main
for i in range(len(A)):
print(A[i])
Kết quả
a i l o r t t u
Ở đây chúng ta nhận được đầu ra từ thuật toán theo thứ tự tăng dần. Min_ là giá trị hiện tại được so sánh với tất cả các giá trị khác. Các tham số phân tích thuật toán được liệt kê dưới đây:
- Time Complexity – O(n^2)
- Auxiliary Space – O(1)
Tất cả biến được khai báo trong khung toàn cục như hình dưới đây:
Kết luận
Trong bài viết này, chúng ta đã học về Selection sort và triển khai của nó trong Python 3.x hoặc trước đó.