Chương trình tìm số lần dịch chuyển khi sắp xếp chèn (insertion sort) trong Python

Cho mảng, thực hiện insertion sort. Mỗi phần tử được dịch chuyển đến vị trí đúng. Đếm tổng số lần dịch chuyển (shifts). Nếu mảng đã sắp xếp → 0.

Ví dụ: → kết quả .

[4, 5, 3, 1, 2] = 0 shifts
[4, 5, 3, 1, 2] = 0 shifts
[3, 4, 5, 1, 2] = 2 shifts
[1, 3, 4, 5, 2] = 3 shifts
[1, 2, 3, 4, 5] = 3 shifts
Total = 8

Thuật toán giải quyết (Binary Indexed Tree / Fenwick Tree O(n log MAX))

1. Khởi tạo mảng kích thước 1,000,001 (Fenwick tree)
2. Duyệt từng trong mảng:
   • Truy vấn: cộng cho (tổng tiền tố)
   • Cập nhật: tăng cho
3. Tổng cặp nghịch thế =
4. Trả về kết quả

Số dịch chuyển insertion sort = số cặp nghịch thế (inversions).

Ví dụ minh họa

def solve(input_arr):
    length = len(input_arr)
    temp_arr = [0] * 1000001
    ans = 0
    for item in input_arr:
        val = item
        while val > 0:
            ans += temp_arr[val]
            val -= val & -val
        val = item
        while val <= 1000000:
            temp_arr[val] = temp_arr[val] + 1
            val += val & -val
    ans = length * (length - 1) // 2 - ans
    return ans

print(solve([4, 5, 3, 1, 2]))

Đầu vào

[4, 5, 3, 1, 2]

Đầu ra

8