🔢 Как посчитать количество инверсий в массиве Python?

Количество инверсий в массиве в Python можно посчитать с помощью алгоритма слияния.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr, 0
    
    mid = len(arr) // 2
    left, inversion_left = merge_sort(arr[:mid])
    right, inversion_right = merge_sort(arr[mid:])
    merged, inversion_merge = merge(left, right)
    
    total_inversions = inversion_left + inversion_right + inversion_merge
    return merged, total_inversions

def merge(left, right):
    merged = []
    inversion_count = 0
    i, j = 0, 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            inversion_count += len(left) - i
            j += 1
    
    merged += left[i:]
    merged += right[j:]
    
    return merged, inversion_count

arr = [4, 2, 1, 3, 5]
sorted_arr, inversions = merge_sort(arr)
print(f"Количество инверсий в массиве: {inversions}")
  

В данном примере используется рекурсивная реализация алгоритма слияния. Основная идея заключается в разделении исходного массива на две равные части, сортировке их отдельно и затем объединении отсортированных массивов.

Во время слияния, если элемент из правой части массива меньше элемента из левой части, то это инверсия. В этом случае, мы увеличиваем счетчик инверсий на количество оставшихся элементов в левой части массива.

После завершения сортировки, в переменной "inversions" будет содержаться общее количество инверсий в массиве.

Как посчитать количество инверсий в массиве Python

Инверсия в массиве происходит, когда два элемента находятся в неправильном порядке. Например, в массиве [2, 4, 1, 3, 5] инверсиями будут (2, 1) и (4, 1). Очень важно уметь считать количество инверсий, особенно при работе с алгоритмами сортировки и поиска.

Существует несколько подходов к поиску количества инверсий в массиве, и мы разберём два из них - алгоритм слияния и метод Пузырька.

Алгоритм слияния

Алгоритм слияния работает путем разделения массива на две половины, сортировки каждой половины и затем слияния их в один отсортированный массив. Во время слияния мы подсчитываем количество инверсий.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    left = merge_sort(left)
    right = merge_sort(right)

    return merge(left, right)

def merge(left, right):
    result = []
    count = 0
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
            count += len(left) - i

    result.extend(left[i:])
    result.extend(right[j:])

    return result, count

arr = [2, 4, 1, 3, 5]
sorted_arr, inversions = merge_sort(arr)
print(f"Количество инверсий: {inversions}")

В этом коде мы сначала разделяем массив пополам и вызываем рекурсивно функцию merge_sort для каждой половины. Затем мы вызываем функцию merge, которая сливает две отсортированные половины в один отсортированный массив. Во время слияния мы считаем количество инверсий.

Метод Пузырька

В методе Пузырька мы проходим по массиву и меняем местами соседние элементы, если они находятся в неправильном порядке. При каждом обмене мы увеличиваем счетчик инверсий. Этот метод прост в реализации, но не является эффективным для больших массивов.

def bubble_sort(arr):
    inversions = 0
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                inversions += 1

    return inversions

arr = [2, 4, 1, 3, 5]
inversions = bubble_sort(arr)
print(f"Количество инверсий: {inversions}")

В этом коде мы используем вложенные циклы, чтобы пройти по массиву и менять местами соседние элементы, если они не соответствуют порядку сортировки. За каждый обмен мы увеличиваем счетчик инверсий. В конце мы получаем количество инверсий в переменной inversions.

Оба этих метода позволяют нам эффективно считать количество инверсий в массиве. Алгоритм слияния обычно предпочтительнее для больших массивов, потому что имеет лучшую временную сложность O(n log n). Однако метод Пузырька может быть полезен для небольших массивов или в случаях, когда у нас есть ограничения на использование дополнительной памяти.

Заключение

Теперь вы знаете, как посчитать количество инверсий в массиве Python при помощи двух различных методов. Алгоритм слияния обеспечивает лучшую производительность для больших массивов, в то время как метод Пузырька может быть удобен для небольших массивов или в случаях с ограничениями на использование памяти. Используйте эти методы в зависимости от требований вашей задачи, и вы сможете эффективно работать с инверсиями в массивах.