Chương trình Python Recursive Insertion Sort (Sắp xếp chèn đệ quy)

Trong bài viết này, chúng ta sẽ tìm hiểu giải pháp cho bài toán sau:

Đề bài – Cho một mảng, cần sắp xếp dùng thuật toán Insertion Sort đệ quy.

Insertion Sort tạo mảng song song, chèn thủ công các phần tử theo thứ tự.

Hãy quan sát giải pháp trong triển khai dưới đây:

Ví dụ

# cách đệ quy
def insertionSortRecursive(arr, n):
    # base case
    if n <= 1:
        return
    # Sắp xếp n-1 phần tử đầu
    insertionSortRecursive(arr, n-1)
    last = arr[n-1]
    j = n-2
    # dịch chuyển
    while (j >= 0 and arr[j] > last):
        arr[j+1] = arr[j]
        j = j-1
    arr[j+1] = last

# main
arr = [1, 5, 3, 4, 8, 6, 3, 4, 5]
n = len(arr)
insertionSortRecursive(arr, n)
print("Mảng đã sắp xếp:")
for i in range(n):
    print(arr[i], end=" ")

Kết quả

Mảng đã sắp xếp: 1 3 3 4 4 5 5 6 8

Kết luận

Trong bài này, chúng ta đã học cách làm chương trình Python Recursive Insertion Sort.