Chương trình Python đếm số đảo ngược (inversions) trong mảng

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 list, cần đếm số lượng inversion (cặp đảo ngược) và hiển thị.

Inversion count là số bước cần để sắp xếp mảng.

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

Ví dụ

# đếm inversion
def InvCount(arr, n):
    inv_count = 0
    for i in range(n):
        for j in range(i + 1, n):
            if (arr[i] > arr[j]):
                inv_count += 1
    return inv_count

# Driver Code
arr = [1, 5, 3, 8, 7]
n = len(arr)
print("Tổng số inversion:", InvCount(arr, n))

Kết quả

Tổng số inversion: 2

Kết luận

Trong bài này, chúng ta đã học cách làm chương trình Python đếm inversion trong mảng.