Chương trình Python thực hiện Sắp xếp chèn (Insertion Sort)

Trong bài viết này, chúng ta sẽ tìm hiểu về triển khai Sắp xếp chèn trong Python 3.x hoặc các phiên bản trước đó.

Thuật toán

1. Lặp qua các phần tử đầu vào bằng cách mở rộng mảng đã sắp xếp ở mỗi lần lặp.
2. So sánh phần tử hiện tại với giá trị lớn nhất có sẵn trong mảng đã sắp xếp.
3. Nếu phần tử hiện tại lớn hơn, để nó ở chỗ và chuyển sang phần tử tiếp theo; ngược lại tìm vị trí đúng trong mảng đã sắp xếp và di chuyển nó đến vị trí đó.
4. Điều này đạt được bằng cách dịch chuyển tất cả các phần tử lớn hơn phần tử hiện tại trong mảng đã sắp xếp sang phải một vị trí.

Bây giờ 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:

Ví dụ

def insertionSort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        # Di chuyển các phần tử arr[0..i-1] lớn hơn key
        # sang một vị trí trước vị trí hiện tại
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

# main
arr = ['t', 'u', 't', 'o', 'r', 'i', 'a', 'l']
insertionSort(arr)
print("Mảng đã sắp xếp:")
for i in range(len(arr)):
    print(arr[i])

Kết quả

Mảng đã sắp xếp: a i l o r t t u

Độ phức tạp thời gian − O(n²)

Không gian phụ trợ − O(1)

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ề 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 đó.