Contar inversões usando ordenamento por intercalação modificado
Conte o número de inversões em um vetor — pares em que a[i] > a[j] e i < j — contando as inversões entre partições durante a etapa de intercalação.
Contar inversões usando ordenamento por intercalação modificado é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 2 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
O que é uma Inversão?
Uma inversão em um vetor é um par de índices (i, j) em que i < j, mas a[i] > a[j] — um elemento maior aparece antes de um menor. Por exemplo, em [3, 1, 2], as inversões são (3,1) e (3,2), portanto há 2 inversões. Um vetor ordenado tem 0 inversões. Um vetor de n elementos ordenado em ordem inversa tem n(n-1)/2 inversões. Contar inversões mede o quanto um vetor está distante da ordem ordenada.
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]Abordagem Ingênua O(n²)
A abordagem de força bruta verifica todos os pares (i, j) com i < j e conta aqueles em que a[i] > a[j]. Ela usa tempo O(n²) e espaço O(1). Para n = 10⁵, isso significa 5 × 10⁹ comparações — lento demais. A abordagem de divisão e conquista usando uma ordenação por intercalação modificada resolve o problema em O(n log n). A ideia principal é que, durante a etapa de intercalação da ordenação por intercalação, podemos contar com eficiência as inversões entre as duas partes.
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])) # 3A Intuição da Ordenação por Intercalação
Durante a intercalação de duas metades ordenadas L e R, se escolhermos o elemento R[j] em vez de L[i] (porque R[j] < L[i]), então todos os elementos restantes em L, a partir do índice i, também são maiores que R[j]. Isso acontece porque L está ordenada. Portanto, cada vez que retiramos um elemento da metade direita, contamos len(L) - i inversões entre as metades. Essa contagem não tem custo adicional — ela acontece durante a intercalação normal.
# 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')Implementação da Ordenação por Intercalação Modificada
Modifique a ordenação por intercalação para retornar tanto o vetor ordenado quanto a contagem de inversões. O total de inversões = inversões da metade esquerda + inversões da metade direita + inversões entre as metades encontradas durante a intercalação. O caso-base retorna (um único elemento, 0 inversões). A função merge conta as inversões enquanto faz a intercalação. Tempo total: 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])) # 3Rastreando o Algoritmo
Acompanhe [2, 4, 1, 3]: divida em [2, 4] e [1, 3]. Ordenação da parte esquerda: [2, 4] → ordenado [2,4], 0 inversões. Ordenação da parte direita: [1, 3] → ordenado [1,3], 0 inversões. Intercale [2,4] e [1,3]: pegue 1 (count += 2 para 2>1 e 4>1), pegue 2 (sem contagem), pegue 3 (count += 1 para 4>3), pegue 4. Inversões entre as metades = 3. Total = 0+0+3 = 3. Verificação: pares (2,1), (4,1), (4,3) = 3 inversões. ✓
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]))Por que as Inversões entre as Metades são Capturadas Corretamente
Correção: qualquer par de inversão (a[i], a[j]) em que i < j pertence exatamente a uma de três categorias: (1) ambos estão na metade esquerda — contado pela chamada recursiva da esquerda; (2) ambos estão na metade direita — contado pela chamada recursiva da direita; (3) o elemento da metade esquerda é > que o elemento da metade direita — contado durante a intercalação como uma inversão entre as metades. As categorias são mutuamente exclusivas e exaustivas, portanto nenhuma inversão é contada duas vezes nem deixada de contar. Esse argumento de particionamento é a prova padrão de correção para D&C.
# 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!')Aplicações da Contagem de Inversões
As inversões medem o grau de ordenação. Aplicações: (1) Correlação de classificações: a distância tau de Kendall entre duas listas classificadas é o número de inversões. (2) Eficiência da ordenação por inserção: a ordenação por inserção faz exatamente tantas trocas quanto o número de inversões. (3) Análise da ordenação por bolha: cada passagem da ordenação por bolha reduz o número de inversões; o número de passagens necessárias é igual ao número de inversões. (4) Solubilidade de quebra-cabeças: um quebra-cabeça de 8 ou de 15 peças é solucionável se e somente se o número de inversões tiver uma paridade específica.
# 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 disagreementRelacionado: Contar Números Menores Depois de Si
Contar Números Menores Depois de Si (LeetCode 315) pergunta, para cada elemento, quantos elementos à sua direita são menores. Essa é uma contagem de inversões por elemento. O problema pode ser resolvido com a mesma ordenação por intercalação modificada, rastreando quais índices originais estão sendo contados. Como alternativa, use uma Árvore Indexada Binária (Árvore de Fenwick) ou uma ordenação por intercalação com rastreamento de índices. A abordagem de D&C é executada em 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]Pares Reversos
Pares Reversos (LeetCode 493) conta pares (i, j) em que i < j e nums[i] > 2 × nums[j]. A contagem padrão de inversões usa nums[i] > nums[j]. Aqui, o limiar muda para 2 × nums[j]. Modifique a ordenação por intercalação: conte entre as divisões antes de intercalar (use dois ponteiros para contar enquanto a metade esquerda ainda tiver elementos válidos) e, depois, intercale normalmente. O custo total é 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])) # 3Contagem de inversões globais versus locais
Inversões globais e locais (LeetCode 775): dado um vetor que é uma permutação de 0..n-1, determine se o número de inversões globais (todos os pares i<j com a[i]>a[j]) é igual ao número de inversões locais (pares adjacentes). A ideia principal é que toda inversão local também é global; portanto, global ≥ local. Elas são iguais se, e somente se, não houver inversões não adjacentes — isto é, nenhum elemento estiver a mais de 1 posição de distância de seu índice na ordenação. Isso se reduz a verificar abs(a[i] - i) ≤ 1 para todo 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]Resumo da complexidade da contagem de inversões
Resumo: a contagem de inversões por força bruta é O(n²). A ordenação por intercalação modificada alcança O(n log n) ao contar as inversões entre as partes durante a etapa de intercalação. O custo adicional é O(1) por comparação (adicionando o número de elementos restantes no lado esquerdo), portanto, o custo total adicional é O(n) por nível de intercalação — igual ao da ordenação por intercalação padrão. O espaço é O(n) para os vetores auxiliares. Este é o exemplo clássico do uso de divisão e conquista para contar estatísticas de ordem em tempo linearítmico.
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')Verificação rápida
Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação desta lição.
Recapitulação da lição
Nesta lição, você aprendeu que: as inversões medem o quanto um vetor está desordenado, com força bruta em O(n²) e divisão e conquista em O(n log n); a ordenação por intercalação modificada conta as inversões entre as metades adicionando o número de elementos restantes no lado esquerdo sempre que um elemento do lado direito é escolhido em vez de um elemento do lado esquerdo; e a correção depende da partição: as inversões dentro da parte esquerda, dentro da parte direita e entre as partes são mutuamente exclusivas e, juntas, abrangem todas as inversões. A seguir, exploraremos o algoritmo de votação de Boyer-Moore para encontrar o elemento majoritário.
Perguntas Frequentes
A aula “Contar inversões usando ordenamento por intercalação modificado” é grátis?
Sim — o texto completo de “Contar inversões usando ordenamento por intercalação modificado” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Contar inversões usando ordenamento por intercalação modificado”?
Conte o número de inversões em um vetor — pares em que a[i] > a[j] e i < j — contando as inversões entre partições durante a etapa de intercalação. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 2 de 4.
Quanto tempo leva a aula “Contar inversões usando ordenamento por intercalação modificado”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Modelo de divisão e conquista
- Contar inversões usando ordenamento por intercalação modificado
- Elemento majoritário: votação de Boyer-Moore
- Mediana de dois vetores ordenados