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

Trong bài viết này, chúng ta sẽ học về triển khai Insertion sort trong Python 3.x hoặc trước đó.

Thuật toán

• 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.
• 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.
• Nếu phần tử hiện tại lớn hơn, nó để nguyên vị trí và chuyển sang phần tử tiếp theo, ngược lại nó tìm vị trí đúng trong mảng đã sắp xếp và di chuyển nó đến vị trí đó.
• Đ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("The sorted array is:")
for i in range(len(arr)):
    print(arr[i])

Kết quả

The sorted array is:
a i l o r t t u

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ề Insertion sort và triển khai của nó trong Python 3.x hoặc trước đó.