Trong bài viết này, chúng ta sẽ tìm hiểu về Sắp xếp chọn và triển khai của nó trong Python 3.x hoặc các phiên bản 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_idx = i
for j in range(i + 1, len(A)):
if A[min_idx] > A[j]:
min_idx = j
# Hoán đổi
A[i], A[min_idx] = A[min_idx], 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_idx là giá trị hiện tại đang được so sánh với tất cả các giá trị khác. Các tham số phân tích của thuật toán được liệt kê dưới đây:
Độ phức tạp thời gian − O(n²)
Không gian phụ trợ − O(1)
Ở đây tất cả biến được khai báo trong khung toàn cục như hình bên dưới:
Kết luận
Trong bài viết này, chúng ta đã tìm hiểu về Selection sort và triển khai của nó trong Python 3.x hoặc các phiên bản trước đó.