Подсчёт инверсий с помощью изменённой сортировки слиянием
Подсчитайте число инверсий в массиве — пар, для которых a[i] > a[j] и i < j, — подсчитывая инверсии между разделёнными частями во время слияния
«Подсчёт инверсий с помощью изменённой сортировки слиянием» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Что такое инверсия?
Инверсия в массиве — это пара индексов (i, j), для которой i < j, но a[i] > a[j]: больший элемент расположен перед меньшим. Например, в массиве [3, 1, 2] инверсиями являются пары (3,1) и (3,2), поэтому всего их 2. В отсортированном массиве 0 инверсий. В обратно отсортированном массиве из n элементов имеется n(n-1)/2 инверсий. Подсчёт инверсий показывает, насколько массив далёк от отсортированного порядка.
arr = [3, 1, 2]
# Inversions: pairs (i,j) where i<j and arr[i]>arr[j]
inversions = []
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] > arr[j]:
inversions.append((arr[i], arr[j]))
print('Inversions in', arr, ':', inversions)
print('Count:', len(inversions)) # 2
# Maximum inversions in n-element array:
import math
n = 5
print(f'Max inversions for n={n}: {n*(n-1)//2}') # 10 for [5,4,3,2,1]Наивный подход за O(n²)
Подход с полным перебором проверяет все пары (i, j), где i < j, и подсчитывает те, для которых a[i] > a[j]. Он использует время O(n²) и память O(1). При n = 10⁵ это означает 5 × 10⁹ сравнений — слишком медленно. Подход «разделяй и властвуй» с использованием модифицированной сортировки слиянием решает задачу за O(n log n). Ключевая идея состоит в том, что во время шага слияния сортировки слиянием можно эффективно подсчитывать инверсии между половинами.
def count_inversions_brute(arr):
n = len(arr)
count = 0
for i in range(n):
for j in range(i + 1, n):
if arr[i] > arr[j]:
count += 1
return count
print(count_inversions_brute([3, 1, 2])) # 2
print(count_inversions_brute([5, 4, 3, 2, 1])) # 10
print(count_inversions_brute([1, 2, 3, 4, 5])) # 0
print(count_inversions_brute([2, 4, 1, 3, 5])) # 3Идея сортировки слиянием
При слиянии двух отсортированных половин L и R, если мы выбираем элемент R[j] вместо L[i] (потому что R[j] < L[i]), то все оставшиеся элементы в L, начиная с индекса i, также больше R[j]. Это верно, поскольку L отсортирован. Поэтому каждый раз, когда мы берём элемент из правой половины, нужно добавить к счётчику инверсий между половинами количество элементов в L − i. Этот подсчёт выполняется бесплатно — прямо во время обычного слияния.
# During merge of [1, 3, 5] and [2, 4, 6]:
# Compare L[0]=1 vs R[0]=2: take L[0]=1, no inversions
# Compare L[1]=3 vs R[0]=2: take R[0]=2, inversions += len(L)-1 = 2 (3>2, 5>2)
# Compare L[1]=3 vs R[1]=4: take L[1]=3, no inversions
# Compare L[2]=5 vs R[1]=4: take R[1]=4, inversions += len(L)-2 = 1 (5>4)
# Compare L[2]=5 vs R[2]=6: take L[2]=5, no inversions
# Take R[2]=6
# Total cross-inversions = 2 + 1 = 3
print('Cross-inversions identified during merge: 3')Реализация модифицированной сортировки слиянием
Измените сортировку слиянием так, чтобы она возвращала и отсортированный массив, и количество инверсий. Общее число инверсий = инверсии в левой половине + инверсии в правой половине + инверсии между половинами, найденные во время слияния. Базовый случай возвращает кортеж (один элемент, 0 инверсий). Функция слияния подсчитывает инверсии по мере слияния. Общее время работы: O(n log n).
def count_inversions(arr):
def merge_sort_count(arr):
if len(arr) <= 1:
return arr, 0
mid = len(arr) // 2
left, left_count = merge_sort_count(arr[:mid])
right, right_count = merge_sort_count(arr[mid:])
merged, cross_count = merge_count(left, right)
return merged, left_count + right_count + cross_count
def merge_count(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 # all remaining in left are inversions
result += left[i:] + right[j:]
return result, count
_, total = merge_sort_count(arr)
return total
print(count_inversions([3, 1, 2])) # 2
print(count_inversions([5, 4, 3, 2, 1])) # 10
print(count_inversions([2, 4, 1, 3, 5])) # 3Трассировка алгоритма
Проследим работу на примере [2, 4, 1, 3]: разделим его на [2, 4] и [1, 3]. Сортировка левой части: [2, 4] → отсортированный [2,4], 0 инверсий. Сортировка правой части: [1, 3] → отсортированный [1,3], 0 инверсий. Слияние [2,4] и [1,3]: берём 1 (увеличиваем счётчик на 2 для 2>1 и 4>1), берём 2 (счётчик не изменяется), берём 3 (увеличиваем счётчик на 1 для 4>3), берём 4. Инверсий между половинами = 3. Всего = 0+0+3 = 3. Проверка: пары (2,1), (4,1), (4,3) дают 3 инверсии. ✓
def count_with_trace(arr):
def ms(arr, depth=0):
indent = ' ' * depth
if len(arr) <= 1: return arr, 0
mid = len(arr) // 2
L, lc = ms(arr[:mid], depth+1)
R, rc = ms(arr[mid:], depth+1)
merged, cc = merge_c(L, R)
print(f'{indent}merge({L},{R}) → cross={cc}')
return merged, lc + rc + cc
def merge_c(L, R):
res, c, i, j = [], 0, 0, 0
while i < len(L) and j < len(R):
if L[i] <= R[j]: res.append(L[i]); i += 1
else: res.append(R[j]); j += 1; c += len(L) - i
return res + L[i:] + R[j:], c
_, total = ms(arr)
return total
print('Total inversions:', count_with_trace([2, 4, 1, 3]))Почему инверсии между половинами подсчитываются правильно
Корректность: любая пара-инверсия (a[i], a[j]), где i < j, относится ровно к одной из трёх категорий: (1) оба элемента находятся в левой половине — их подсчитывает рекурсивный вызов для левой части; (2) оба элемента находятся в правой половине — их подсчитывает рекурсивный вызов для правой части; (3) элемент левой половины больше элемента правой половины — такая инверсия подсчитывается во время слияния как инверсия между половинами. Категории взаимно исключают друг друга и охватывают все случаи, поэтому ни одна инверсия не подсчитывается дважды и ни одна не пропускается. Такое разбиение является стандартным доказательством корректности метода РиВ.
# Verification: compare with brute force on random arrays
import random
def count_brute(arr):
n = len(arr)
return sum(1 for i in range(n) for j in range(i+1,n) if arr[i]>arr[j])
def count_dc(arr):
def ms(a):
if len(a)<=1: return a, 0
m=len(a)//2
L,lc=ms(a[:m]); R,rc=ms(a[m:])
res,c,i,j=[],0,0,0
while i<len(L) and j<len(R):
if L[i]<=R[j]: res.append(L[i]);i+=1
else: res.append(R[j]);j+=1;c+=len(L)-i
return res+L[i:]+R[j:],(lc+rc+c)
return ms(arr)[1]
for _ in range(100):
arr = random.choices(range(20), k=random.randint(1,10))
assert count_dc(arr[:]) == count_brute(arr), 'MISMATCH!'
print('All 100 random tests passed!')Применения подсчёта инверсий
Инверсии измеряют отсортированность. Применения: (1) корреляция рангов: расстояние Кендалла — тау между двумя ранжированными списками равно числу инверсий; (2) эффективность сортировки вставками: сортировка вставками выполняет ровно столько обменов, сколько имеется инверсий; (3) анализ пузырьковой сортировки: каждый проход пузырьковой сортировки уменьшает число инверсий, а необходимое количество проходов равно числу инверсий; (4) разрешимость головоломки: головоломка «8» или «15» разрешима тогда и только тогда, когда число инверсий имеет определённую чётность.
# Kendall tau: number of inversions between two rankings
# Useful for comparing search result rankings or recommendation systems
def kendall_tau(rank1, rank2):
'''Count inversions where rank1 and rank2 disagree on relative order.'''
# Map rank2 positions to create a comparison sequence
pos = {v: i for i, v in enumerate(rank2)}
# Convert rank1 to position-in-rank2 ordering
arr = [pos[v] for v in rank1]
return count_inversions(arr)
def count_inversions(arr):
def ms(a):
if len(a)<=1: return a,0
m=len(a)//2; L,lc=ms(a[:m]); R,rc=ms(a[m:])
res,c,i,j=[],0,0,0
while i<len(L) and j<len(R):
if L[i]<=R[j]: res.append(L[i]);i+=1
else: res.append(R[j]);j+=1;c+=len(L)-i
return res+L[i:]+R[j:],(lc+rc+c)
return ms(arr[:])[1]
print(kendall_tau([1,2,3],[3,1,2])) # measures disagreementСвязано: подсчёт меньших чисел после текущего
Подсчёт меньших чисел после текущего (LeetCode 315) спрашивает для каждого элемента: сколько меньших элементов находится справа от него? Это подсчёт инверсий для каждого элемента. Задачу можно решить с помощью той же модифицированной сортировки слиянием, отслеживая исходные индексы, которые были подсчитаны. Другие варианты — двоичное индексированное дерево (дерево Фенвика) или сортировка слиянием с отслеживанием индексов. Подход РиВ работает за O(n log n).
def count_smaller(nums):
n = len(nums)
result = [0] * n
indexed = list(enumerate(nums))
def merge_sort(arr):
if len(arr) <= 1: return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
merged = []
i = j = 0
while i < len(left) and j < len(right):
if left[i][1] <= right[j][1]:
# left[i] is placed; j elements from right are smaller and to the right
result[left[i][0]] += j
merged.append(left[i]); i += 1
else:
merged.append(right[j]); j += 1
while i < len(left):
result[left[i][0]] += j # all of right is smaller
merged.append(left[i]); i += 1
return merged + right[j:]
merge_sort(indexed)
return result
print(count_smaller([5, 2, 6, 1])) # [2, 1, 1, 0]Обратные пары
Обратные пары (LeetCode 493) подсчитывает пары (i, j), для которых i < j и nums[i] > 2 × nums[j]. В стандартном подсчёте инверсий используется условие nums[i] > nums[j]. Здесь порог изменяется на 2 × nums[j]. Измените сортировку слиянием: сначала подсчитайте пары между половинами (используйте два указателя, чтобы подсчитывать элементы, пока в левой половине остаются подходящие элементы), а затем выполните обычное слияние. Общее время работы — O(n log n).
def reverse_pairs(nums):
def merge_sort_count(arr):
if len(arr) <= 1: return arr, 0
mid = len(arr) // 2
L, lc = merge_sort_count(arr[:mid])
R, rc = merge_sort_count(arr[mid:])
# Count cross pairs: L[i] > 2*R[j]
j = 0
cross = 0
for l_val in L:
while j < len(R) and l_val > 2 * R[j]:
j += 1
cross += j
# Normal merge (separate from count)
merged = []
i = jj = 0
while i < len(L) and jj < len(R):
if L[i] <= R[jj]: merged.append(L[i]); i += 1
else: merged.append(R[jj]); jj += 1
merged += L[i:] + R[jj:]
return merged, lc + rc + cross
return merge_sort_count(nums)[1]
print(reverse_pairs([1, 3, 2, 3, 1])) # 2
print(reverse_pairs([2, 4, 3, 5, 1])) # 3Глобальные и локальные инверсии
Глобальные и локальные инверсии (LeetCode 775): если дана перестановка чисел от 0 до n-1, определите, равно ли число глобальных инверсий (всех пар i<j, для которых a[i]>a[j]) числу локальных инверсий (соседних пар). Ключевая идея: каждая локальная инверсия также является глобальной, поэтому глобальных инверсий не меньше, чем локальных. Они равны тогда и только тогда, когда нет инверсий между несоседними элементами — то есть ни один элемент не отстоит от своего индекса в отсортированном массиве более чем на 1 позицию. Таким образом, достаточно проверить abs(a[i] - i) ≤ 1 для всех i.
def is_ideal_permutation(A):
'''Global inversions == local inversions
iff no element is more than 1 position from its sorted index.'''
return all(abs(a - i) <= 1 for i, a in enumerate(A))
print(is_ideal_permutation([1, 0, 2])) # True
print(is_ideal_permutation([1, 2, 0])) # False (A[0]=1 is far from 2, A[2]=0 is far)
# Verification with inversion counts
print(count_inversions([1, 0, 2])) # 1 (global)
local1 = sum(1 for i in range(len([1,0,2])-1) if [1,0,2][i]>[1,0,2][i+1])
print('local:', local1) # 1 (equal)
def count_inversions(arr):
def ms(a):
if len(a)<=1: return a,0
m=len(a)//2; L,lc=ms(a[:m]); R,rc=ms(a[m:])
res,c,i,j=[],0,0,0
while i<len(L) and j<len(R):
if L[i]<=R[j]: res.append(L[i]);i+=1
else: res.append(R[j]);j+=1;c+=len(L)-i
return res+L[i:]+R[j:],(lc+rc+c)
return ms(arr[:])[1]Сводка по сложности подсчёта инверсий
Сводка: полный перебор подсчёта инверсий имеет сложность O(n²). Модифицированная сортировка слиянием достигает сложности O(n log n), подсчитывая инверсии между частями во время слияния. Дополнительная стоимость составляет O(1) на сравнение: добавляется len(left) - i, поэтому суммарные дополнительные затраты составляют O(n) на каждом уровне слияния — столько же, сколько в стандартной сортировке слиянием. Для вспомогательных массивов требуется O(n) памяти. Это классический пример применения метода «разделяй и властвуй» для подсчёта порядковых статистик за линейно-логарифмическое время.
import time, random
def time_method(func, arr):
start = time.time()
result = func(arr[:])
return result, time.time() - start
def count_brute(arr):
return sum(1 for i in range(len(arr)) for j in range(i+1,len(arr)) if arr[i]>arr[j])
def count_dc(arr):
def ms(a):
if len(a)<=1: return a,0
m=len(a)//2;L,lc=ms(a[:m]);R,rc=ms(a[m:])
res,c,i,j=[],0,0,0
while i<len(L) and j<len(R):
if L[i]<=R[j]: res.append(L[i]);i+=1
else: res.append(R[j]);j+=1;c+=len(L)-i
return res+L[i:]+R[j:],(lc+rc+c)
return ms(arr[:])[1]
arr = random.sample(range(1000), 1000)
r1, t1 = time_method(count_brute, arr)
r2, t2 = time_method(count_dc, arr)
print(f'Brute: {r1} in {t1:.4f}s')
print(f'D&C: {r2} in {t2:.4f}s')
print(f'Speedup: {t1/t2:.1f}x')Быстрая проверка
Проверьте своё понимание концепций курса «Структуры данных & алгоритмы — подготовка к собеседованию по программированию» из этого урока.
Итоги урока
В этом уроке Вы узнали: инверсии показывают, насколько массив не отсортирован: полный перебор занимает O(n²), а метод «разделяй и властвуй» — O(n log n), модифицированная сортировка слиянием подсчитывает инверсии между половинами, добавляя количество элементов слева минус i каждый раз, когда элемент из правой части выбирается раньше элемента из левой, а корректность опирается на разбиение: инверсии внутри левой части, внутри правой части и между частями не пересекаются и вместе охватывают все инверсии. Далее мы рассмотрим алгоритм голосования Бойера—Мура для поиска мажоритарного элемента.
Часто задаваемые вопросы
Урок «Подсчёт инверсий с помощью изменённой сортировки слиянием» бесплатный?
Да — полный текст урока «Подсчёт инверсий с помощью изменённой сортировки слиянием» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Подсчёт инверсий с помощью изменённой сортировки слиянием»?
Подсчитайте число инверсий в массиве — пар, для которых a[i] > a[j] и i < j, — подсчитывая инверсии между разделёнными частями во время слияния Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.
Сколько времени занимает урок «Подсчёт инверсий с помощью изменённой сортировки слиянием»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Шаблон «Разделяй и властвуй»
- Подсчёт инверсий с помощью изменённой сортировки слиянием
- Элемент большинства: голосование Бойера—Мура
- Медиана двух отсортированных массивов