Compter les inversions avec un tri fusion modifié
Comptez le nombre d’inversions dans un tableau — des paires telles que a[i] > a[j] et i < j — en comptant les inversions entre partitions lors de la fusion.
Compter les inversions avec un tri fusion modifié est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 2 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu’est-ce qu’une inversion ?
Une inversion dans un tableau est une paire d’indices (i, j) telle que i < j mais a[i] > a[j] : un élément plus grand apparaît avant un élément plus petit. Par exemple, dans [3, 1, 2], les inversions sont (3,1) et (3,2), soit 2 inversions. Un tableau trié contient 0 inversion. Un tableau de n éléments trié dans l’ordre inverse contient n(n-1)/2 inversions. Le comptage des inversions mesure l’écart entre un tableau et l’ordre trié.
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]Approche naïve en O(n²)
L’approche par force brute examine toutes les paires (i, j) telles que i < j et compte celles pour lesquelles a[i] > a[j]. Elle nécessite un temps O(n²) et un espace O(1). Pour n = 10⁵, cela représente 5 × 10⁹ comparaisons, ce qui est trop lent. L’approche diviser pour régner utilisant une variante du tri par fusion résout le problème en O(n log n). L’idée clé est que, pendant l’étape de fusion du tri par fusion, il est possible de compter efficacement les inversions entre les deux parties.
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])) # 3L’idée clé du tri par fusion
Lors de la fusion de deux moitiés triées L et R, si l’on sélectionne l’élément R[j] plutôt que L[i] parce que R[j] < L[i], alors tous les éléments restants de L à partir de l’indice i sont également supérieurs à R[j]. Cela vient du fait que L est trié. Ainsi, chaque fois que l’on prend un élément de la moitié droite, on compte len(L) - i inversions entre les deux moitiés. Ce comptage est gratuit : il s’effectue pendant la fusion normale.
# 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')Implémentation du tri par fusion modifié
Modifiez le tri par fusion pour qu’il renvoie à la fois le tableau trié et le nombre d’inversions. Le nombre total d’inversions = inversions de la moitié gauche + inversions de la moitié droite + inversions entre les deux moitiés trouvées pendant la fusion. Le cas de base renvoie (un seul élément, 0 inversion). La fonction merge compte les inversions pendant la fusion. Temps 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])) # 3Suivre l’algorithme
Suivons [2, 4, 1, 3] : division en [2, 4] et [1, 3]. Tri de la sous-partie gauche : [2, 4] → [2,4] trié, 0 inversion. Tri de la sous-partie droite : [1, 3] → [1,3] trié, 0 inversion. Fusion de [2,4] et [1,3] : prendre 1, ce qui ajoute 2 au compteur pour 2>1 et 4>1 ; prendre 2, sans modifier le compteur ; prendre 3, ce qui ajoute 1 pour 4>3 ; puis prendre 4. Inversions entre les deux moitiés = 3. Total = 0+0+3 = 3. Vérification : paires (2,1), (4,1), (4,3) = 3 inversions. ✓
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]))Pourquoi les inversions entre les deux moitiés sont correctement comptées
Correction : toute paire inversée (a[i], a[j]) telle que i < j appartient exactement à l’une des trois catégories suivantes : (1) les deux éléments se trouvent dans la moitié gauche — comptés par l’appel récursif gauche ; (2) les deux éléments se trouvent dans la moitié droite — comptés par l’appel récursif droit ; (3) l’élément de la moitié gauche est supérieur à celui de la moitié droite — compté pendant la fusion comme inversion entre les deux moitiés. Ces catégories sont mutuellement exclusives et exhaustives : aucune inversion n’est comptée deux fois et aucune n’est oubliée. Cet argument de partition constitue la preuve standard de correction pour le paradigme diviser pour régner.
# 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!')Applications du comptage des inversions
Les inversions mesurent le degré de tri. Applications : (1) corrélation des classements : la distance de Kendall entre deux listes classées correspond au nombre d’inversions ; (2) efficacité du tri par insertion : le tri par insertion effectue exactement autant d’échanges qu’il y a d’inversions ; (3) analyse du tri à bulles : chaque passage du tri à bulles réduit le nombre d’inversions, et le nombre de passages nécessaires est égal au nombre d’inversions ; (4) résolution de casse-têtes : un taquin 8 ou un taquin 15 est soluble si et seulement si le nombre d’inversions possède une parité particulière.
# 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 disagreementAssocié : compter les nombres plus petits situés après chaque élément
Compter les nombres plus petits situés après chaque élément (LeetCode 315) demande, pour chaque élément, combien d’éléments plus petits se trouvent à sa droite. Il s’agit d’un comptage des inversions pour chaque élément. On peut résoudre ce problème avec le même tri par fusion modifié, en conservant la trace des indices d’origine pris en compte. Une autre solution consiste à utiliser un arbre indexé binaire (arbre de Fenwick) ou un tri par fusion avec suivi des indices. L’approche diviser pour régner s’exécute 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]Paires inversées
Paires inversées (LeetCode 493) compte les paires (i, j) telles que i < j et nums[i] > 2 × nums[j]. Le comptage classique des inversions utilise nums[i] > nums[j]. Ici, le seuil devient 2 × nums[j]. Modifiez le tri par fusion : comptez les paires entre les deux parties avant la fusion, en utilisant deux pointeurs pour compter tant que la moitié gauche contient encore des éléments valides, puis effectuez la fusion normalement. Temps 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])) # 3Nombre d’inversions globales et locales
Inversions globales et locales (LeetCode 775) : étant donné une permutation de 0..n-1, déterminez si le nombre d’inversions globales (toutes les paires i<j telles que a[i]>a[j]) est égal au nombre d’inversions locales (paires adjacentes). Idée clé : toute inversion locale est aussi globale, donc le nombre global est supérieur ou égal au nombre local. Ils sont égaux si et seulement s’il n’existe aucune inversion entre éléments non adjacents — autrement dit, aucun élément ne se trouve à plus d’une position de son indice dans le tableau trié. Il suffit donc de vérifier abs(a[i] - i) ≤ 1 pour tout 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]Résumé de la complexité du comptage des inversions
Résumé : le comptage des inversions par force brute est en O(n²). Un tri fusion modifié atteint O(n log n) en comptant les inversions entre les deux parties pendant l’étape de fusion. Le coût supplémentaire est de O(1) par comparaison (en ajoutant len(left) - i), donc la surcharge totale est de O(n) par niveau de fusion — comme pour un tri fusion standard. L’espace mémoire est de O(n) pour les tableaux auxiliaires. Il s’agit de l’exemple classique d’utilisation de la stratégie diviser pour régner afin de compter des statistiques d’ordre en temps quasi-linéaire.
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')Vérification rapide
Testez votre compréhension des concepts de Structures de données & algorithmes — préparation aux entretiens de programmation présentés dans cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris que : les inversions mesurent à quel point un tableau est non trié, avec une force brute en O(n²) et la stratégie diviser pour régner en O(n log n), le tri fusion modifié compte les inversions entre les deux moitiés en ajoutant len(left)-i chaque fois qu’un élément de droite est choisi plutôt qu’un élément de gauche, et la correction repose sur la partition : les inversions de gauche-gauche, de droite-droite et entre les deux parties sont mutuellement exclusives et couvrent ensemble toutes les inversions. Ensuite, nous découvrirons l’algorithme de vote de Boyer-Moore pour trouver l’élément majoritaire.
Questions Fréquemment Posées
La leçon « Compter les inversions avec un tri fusion modifié » est-elle gratuite ?
Oui — le texte complet de « Compter les inversions avec un tri fusion modifié » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Compter les inversions avec un tri fusion modifié » ?
Comptez le nombre d’inversions dans un tableau — des paires telles que a[i] > a[j] et i < j — en comptant les inversions entre partitions lors de la fusion. Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 2 sur 4.
Combien de temps prend la leçon « Compter les inversions avec un tri fusion modifié » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Modèle diviser pour régner
- Compter les inversions avec un tri fusion modifié
- Élément majoritaire : vote de Boyer-Moore
- Médiane de deux tableaux triés