Sắp xếp lựa chọn (Selection sort)

Chọn sắp xếp

Sắp xếp lựa chọn (Selection sort) là một thuật toán sắp xếp đơn giản và trực quan. Nó hoạt động như sau. Đầu tiên tìm phần tử nhỏ nhất (lớn) trong dãy chưa được sắp xếp, lưu trữ nó ở đầu dãy đã sắp xếp, rồi tiếp tục tìm phần tử nhỏ nhất (lớn) từ các phần tử chưa được sắp xếp còn lại, rồi đặt nó ở cuối dãy đã sắp xếp. Và cứ thế, cho đến khi tất cả các phần tử được sắp xếp.

Ưu điểm chính của sắp xếp chọn lọc có liên quan đến sự di chuyển của dữ liệu. Nếu một phần tử ở đúng vị trí cuối cùng, nó sẽ không bị di chuyển. Mỗi lần sắp xếp lựa chọn trao đổi một cặp phần tử, ít nhất một trong số chúng sẽ được chuyển đến vị trí cuối cùng của nó, do đó, việc sắp xếp một bảng gồm n phần tử sẽ thực hiện nhiều nhất n-1 lần trao đổi trong tổng số. Trong số tất cả các phương pháp sắp xếp hoàn toàn dựa vào trao đổi để di chuyển các phần tử, sắp xếp có chọn lọc là một phương pháp rất tốt.

Phân tích xếp hạng lựa chọn

Quy trình sắp xếp:

sự lựa chọn

Màu đỏ cho biết giá trị nhỏ nhất hiện tại, màu vàng cho biết trình tự đã sắp xếp và màu xanh cho biết vị trí hiện tại.

def selection_sort(alist):
    n = len(alist)
    for i in range(n-1):
        min_index = i
        for j in range(i+1, n):
            if alist[j] < alist[min_index]:
                min_index = j
        if min_index != i:
            alist[i], alist[min_index] = alist[min_index], alist[i]

alist = [54,226,93,17,77,31,44,55,20]
selection_sort(alist)
print(alist)

thời gian phức tạp

• Độ phức tạp thời gian tối ưu: O (n 2 )

• Độ phức tạp thời gian tồi tệ nhất: O (n 2 )

• Ổn định: Không ổn định (xem xét lựa chọn lớn nhất theo thứ tự tăng dần mỗi lần)

Chọn bản trình diễn sắp xếp

sự lựa chọn