Sắp xếp chèn(Insertion Sort)

Sắp xếp chèn (tiếng Anh: Insertion Sort) là một thuật toán sắp xếp đơn giản và trực quan. Nguyên lý hoạt động của nó là xây dựng một dãy có thứ tự, đối với dữ liệu chưa được sắp xếp thì quét từ sau ra trước theo dãy đã sắp xếp, tìm vị trí tương ứng và chèn vào. Khi thực hiện sắp xếp chèn, trong quá trình quét từ sau ra trước, cần phải di chuyển lùi nhiều lần các phần tử đã sắp xếp để tạo không gian chèn cho phần tử mới nhất.

Phân tích sắp xếp chè

chèn

def insert_sort(alist):
    for i in range(1, len(alist)):
        for j in range(i, 0, -1):
            if alist[j] < alist[j-1]:
                alist[j], alist[j-1] = alist[j-1], alist[j]

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

thời gian phức tạp

• Độ phức tạp thời gian tối ưu: O (n) (thứ tự tăng dần, trình tự đã có thứ tự tăng dần)

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

• Stability: ổn định

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

chèn