Contar inversiones con merge sort modificado
Cuente el número de inversiones en un array —pares en los que a[i] > a[j] e i < j— contando las inversiones entre particiones durante el paso de combinación.
Contar inversiones con merge sort modificado es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 2 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué es una inversión?
Una inversión en un array es un par de índices (i, j) donde i < j pero a[i] > a[j]: un elemento mayor aparece antes que uno menor. Por ejemplo, en [3, 1, 2], las inversiones son (3,1) y (3,2), por lo que hay 2 inversiones. Un array ordenado tiene 0 inversiones. Un array de n elementos ordenado en sentido inverso tiene n(n-1)/2 inversiones. Contar inversiones mide cuánto se aleja un array del orden ordenado.
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]Enfoque ingenuo O(n²)
El enfoque de fuerza bruta comprueba todos los pares (i, j) con i < j y cuenta aquellos en los que a[i] > a[j]. Utiliza un tiempo O(n²) y un espacio O(1). Para n = 10⁵, esto supone 5 × 10⁹ comparaciones, demasiado lento. El enfoque de divide y vencerás basado en un merge sort modificado lo resuelve en O(n log n). La idea clave es que durante el paso de fusión de merge sort podemos contar eficazmente las inversiones que cruzan la divisió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])) # 3La idea clave de merge sort
Durante la fusión de dos mitades ordenadas L y R, si elegimos el elemento R[j] antes que L[i] (porque R[j] < L[i]), entonces todos los elementos restantes de L desde el índice i en adelante también son mayores que R[j]. Esto se debe a que L está ordenado. Por tanto, cada vez que tomamos un elemento de la mitad derecha, contamos len(L) - i inversiones entre mitades. Este recuento es gratuito: se realiza durante la fusión 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')Implementación de merge sort modificado
Modifique merge sort para que devuelva tanto el array ordenado como el recuento de inversiones. El total de inversiones = inversiones de la mitad izquierda + inversiones de la mitad derecha + inversiones entre mitades encontradas durante la fusión. El caso base devuelve (un solo elemento, 0 inversiones). La función de fusión cuenta las inversiones mientras realiza la fusión. Tiempo 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])) # 3Seguimiento del algoritmo
Trace [2, 4, 1, 3]: divida en [2, 4] y [1, 3]. Ordenación del subarray izquierdo: [2, 4] → array ordenado [2,4], 0 inversiones. Ordenación del subarray derecho: [1, 3] → array ordenado [1,3], 0 inversiones. Fusione [2,4] y [1,3]: tome 1 (count += 2 para 2>1 y 4>1), tome 2 (sin incremento), tome 3 (count += 1 para 4>3) y tome 4. Inversiones entre mitades = 3. Total = 0+0+3 = 3. Verificación: pares (2,1), (4,1), (4,3) = 3 inversiones. ✓
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 qué las inversiones entre mitades se capturan correctamente
Corrección: cualquier par de inversión (a[i], a[j]) donde i < j pertenece exactamente a una de tres categorías: (1) Ambos elementos están en la mitad izquierda: los cuenta la llamada recursiva izquierda. (2) Ambos elementos están en la mitad derecha: los cuenta la llamada recursiva derecha. (3) El elemento de la mitad izquierda es mayor que el de la mitad derecha: se cuenta durante la fusión como una inversión entre mitades. Las categorías son mutuamente excluyentes y exhaustivas, por lo que no se cuenta ninguna inversión dos veces ni se omite ninguna. Este argumento de partición es la demostración estándar de corrección de 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!')Aplicaciones del recuento de inversiones
Las inversiones miden el grado de ordenación. Aplicaciones: (1) Correlación de rankings: la distancia tau de Kendall entre dos listas clasificadas es el número de inversiones. (2) Eficiencia de insertion sort: insertion sort realiza exactamente tantos intercambios como inversiones haya. (3) Análisis de bubble sort: cada pasada de bubble sort reduce las inversiones; el número de pasadas necesarias equivale al número de inversiones. (4) Resolución de puzles: un 8-puzzle o 15-puzzle se puede resolver si y solo si el número de inversiones tiene una paridad 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 después de sí mismos
Count Smaller Numbers After Self (LeetCode 315) pregunta, para cada elemento, cuántos elementos menores hay a su derecha. Es un recuento de inversiones por elemento. Puede resolverse con el mismo merge sort modificado, realizando un seguimiento de los índices originales que se cuentan. Como alternativa, puede utilizar un árbol indexado binario (Fenwick Tree) o un merge sort con seguimiento de índices. El enfoque de D&C se ejecuta en 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 inversos
Reverse Pairs (LeetCode 493) cuenta pares (i, j) donde i < j y nums[i] > 2 × nums[j]. El recuento de inversiones estándar utiliza nums[i] > nums[j]. Aquí, el umbral cambia a 2 × nums[j]. Modifique merge sort: cuente las inversiones entre divisiones antes de fusionar (utilice dos punteros para contar mientras la mitad izquierda aún tenga elementos válidos) y después fusione normalmente. Tiempo 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])) # 3Recuento de inversiones globales frente a locales
Inversiones globales y locales (LeetCode 775): dada una permutación de 0..n-1, determine si el número de inversiones globales (todos los pares i<j con a[i]>a[j]) es igual al número de inversiones locales (pares adyacentes). Idea clave: toda inversión local también es global, por lo que global ≥ local. Son iguales si y solo si no hay inversiones no adyacentes; es decir, ningún elemento está a más de 1 posición de su índice en el array ordenado. Esto se reduce a comprobar 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]Resumen de la complejidad del recuento de inversiones
Resumen: el recuento de inversiones por fuerza bruta es O(n²). El merge sort modificado alcanza O(n log n) al contar las inversiones que cruzan la división durante el paso de combinación. El coste adicional es O(1) por comparación (sumando len(left) - i), por lo que la sobrecarga total es O(n) por nivel de combinación, igual que en el merge sort estándar. El espacio es O(n) para los arrays auxiliares. Este es el ejemplo canónico del uso de D&C para contar estadísticas de orden en tiempo log-lineal.
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')Comprobación rápida
Ponga a prueba su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección ha aprendido: las inversiones miden hasta qué punto un array está desordenado, con O(n²) por fuerza bruta y O(n log n) mediante D&C, el merge sort modificado cuenta las inversiones que cruzan ambas mitades sumando len(left)-i cada vez que se elige un elemento de la derecha en lugar de uno de la izquierda, y la corrección se basa en la partición: las inversiones izquierda-izquierda, derecha-derecha y cruzadas son mutuamente excluyentes y, juntas, abarcan todas las inversiones. A continuación exploraremos el algoritmo de votación de Boyer-Moore para encontrar el elemento mayoritario.
Preguntas frecuentes
¿La lección «Contar inversiones con merge sort modificado» es gratis?
Sí — el texto completo de «Contar inversiones con merge sort modificado» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Contar inversiones con merge sort modificado»?
Cuente el número de inversiones en un array —pares en los que a[i] > a[j] e i < j— contando las inversiones entre particiones durante el paso de combinación. Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 2 de 4.
¿Cuánto tiempo toma la lección «Contar inversiones con merge sort modificado»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Plantilla de divide y vencerás
- Contar inversiones con merge sort modificado
- Elemento mayoritario: votación de Boyer-Moore
- Mediana de dos arrays ordenados