Chương trình Python Binary Insertion Sort

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 Binary Insertion Sort.

Kết hợp tìm kiếm nhị phân (binary search) với insertion sort.

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

Ví dụ

# sort
def insertion_sort(arr):
    for i in range(1, len(arr)):
        temp = arr[i]
        pos = binary_search(arr, temp, 0, i) + 1
        for k in range(i, pos, -1):
            arr[k] = arr[k - 1]
        arr[pos] = temp

def binary_search(arr, key, start, end):
    if end - start <= 1:
        if key < arr[start]:
            return start - 1
        else:
            return start
    mid = (start + end) // 2
    if arr[mid] < key:
        return binary_search(arr, key, mid, end)
    elif arr[mid] > key:
        return binary_search(arr, key, start, mid)
    else:
        return mid

# main
arr = [1, 5, 3, 4, 8, 6, 3, 4]
n = len(arr)
insertion_sort(arr)
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 Binary Insertion Sort.