Inversionen mit modifiziertem Merge Sort zählen
Zählen Sie die Inversionen eines Arrays – Paare, für die a[i] > a[j] und i < j gilt –, indem Sie während des Merge-Schritts die Inversionen zwischen den Teilarrays zählen.
Inversionen mit modifiziertem Merge Sort zählen ist eine kostenlose DSA Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 2 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was ist eine Inversion?
Eine Inversion in einem Array ist ein Indexpaar (i, j), bei dem i < j, aber a[i] > a[j] gilt — ein größeres Element steht vor einem kleineren. Im Beispiel [3, 1, 2] sind die Inversionen (3,1) und (3,2), also gibt es 2 Inversionen. Ein sortiertes Array hat 0 Inversionen. Ein umgekehrt sortiertes Array mit n Elementen hat n(n-1)/2 Inversionen. Das Zählen von Inversionen misst, wie weit ein Array von der sortierten Reihenfolge entfernt ist.
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]Naiver O(n²)-Ansatz
Der Brute-Force-Ansatz überprüft alle Paare (i, j) mit i < j und zählt diejenigen, für die a[i] > a[j] gilt. Dies benötigt O(n²) Zeit und O(1) Speicherplatz. Für n = 10⁵ bedeutet das 5 × 10⁹ Vergleiche — zu langsam. Die Divide-and-Conquer-Methode mit modifiziertem Mergesort löst das Problem in O(n log n). Die zentrale Erkenntnis ist, dass wir während des Zusammenführungsschritts von Mergesort Inversionen zwischen den Hälften effizient zählen können.
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])) # 3Die entscheidende Erkenntnis bei Mergesort
Beim Zusammenführen der beiden sortierten Hälften L und R gilt: Wenn wir das Element R[j] anstelle von L[i] auswählen (weil R[j] < L[i]), sind auch alle verbleibenden Elemente in L ab dem Index i größer als R[j]. Das liegt daran, dass L sortiert ist. Jedes Mal, wenn wir ein Element aus der rechten Hälfte nehmen, zählen wir daher len(L) - i Inversionen zwischen den Hälften. Diese Zählung fällt ohne zusätzlichen Aufwand an — sie erfolgt während des normalen Zusammenführens.
# 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')Implementierung des modifizierten Mergesorts
Passen Sie Mergesort so an, dass sowohl das sortierte Array als auch die Anzahl der Inversionen zurückgegeben werden. Die Gesamtzahl der Inversionen = Inversionen der linken Hälfte + Inversionen der rechten Hälfte + während des Zusammenführens gefundene Inversionen zwischen den Hälften. Der Basisfall gibt (ein einzelnes Element, 0 Inversionen) zurück. Die Merge-Funktion zählt die Inversionen während des Zusammenführens. Gesamtlaufzeit: 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])) # 3Den Algorithmus nachvollziehen
Verfolgen Sie [2, 4, 1, 3]: Teilen Sie das Array in [2, 4] und [1, 3]. Linke Teilsortierung: [2, 4] → sortiert [2,4], 0 Inversionen. Rechte Teilsortierung: [1, 3] → sortiert [1,3], 0 Inversionen. Führen Sie [2,4] und [1,3] zusammen: Nehmen Sie 1 (count += 2 für 2>1 und 4>1), nehmen Sie 2 (keine Zählung), nehmen Sie 3 (count += 1 für 4>3), nehmen Sie 4. Inversionen zwischen den Hälften = 3. Gesamt = 0+0+3 = 3. Überprüfung: Paare (2,1), (4,1), (4,3) = 3 Inversionen. ✓
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]))Warum Inversionen zwischen den Hälften korrekt erfasst werden
Korrektheit: Jedes Inversionspaar (a[i], a[j]) mit i < j gehört genau einer von drei Kategorien an: (1) Beide Elemente liegen in der linken Hälfte — gezählt durch den rekursiven Aufruf für die linke Hälfte. (2) Beide Elemente liegen in der rechten Hälfte — gezählt durch den rekursiven Aufruf für die rechte Hälfte. (3) Das Element der linken Hälfte ist größer als das Element der rechten Hälfte — beim Zusammenführen als Inversion zwischen den Hälften gezählt. Die Kategorien schließen sich gegenseitig aus und sind vollständig, daher wird keine Inversion doppelt gezählt oder übersehen. Dieses Aufteilungsargument ist der Standardbeweis für die Korrektheit von 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!')Anwendungen der Inversionszählung
Inversionen messen den Grad der Sortiertheit. Anwendungen: (1) Rangkorrelation: Die Kendall-Tau-Distanz zwischen zwei Ranglisten entspricht der Anzahl der Inversionen. (2) Effizienz von Insertion Sort: Insertion Sort führt genau so viele Vertauschungen aus, wie es Inversionen gibt. (3) Analyse von Bubble Sort: Jeder Durchlauf von Bubble Sort reduziert die Anzahl der Inversionen; die benötigte Anzahl der Durchläufe entspricht der Anzahl der Inversionen. (4) Lösbarkeit von Puzzles: Ein 8-Puzzle oder 15-Puzzle ist genau dann lösbar, wenn die Anzahl der Inversionen eine bestimmte Parität aufweist.
# 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 disagreementVerwandt: Count Smaller Numbers After Self
Count Smaller Numbers After Self (LeetCode 315) fragt für jedes Element, wie viele rechts davon stehende Elemente kleiner sind. Dabei wird die Anzahl der Inversionen für jedes einzelne Element bestimmt. Das Problem lässt sich mit demselben modifizierten Mergesort lösen, wobei verfolgt wird, welche ursprünglichen Indizes gezählt werden. Alternativ können Sie einen Binary Indexed Tree (Fenwick Tree) oder einen Mergesort mit Indexverfolgung verwenden. Der D&C-Ansatz benötigt O(n log n) Zeit.
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]Reverse Pairs
Reverse Pairs (LeetCode 493) zählt Paare (i, j), für die i < j und nums[i] > 2 × nums[j] gilt. Bei der normalen Inversionszählung wird nums[i] > nums[j] verwendet. Hier ändert sich die Schwelle zu 2 × nums[j]. Passen Sie den Mergesort an: Zählen Sie die Paare über die Teilungsgrenzen hinweg vor dem Zusammenführen (verwenden Sie zwei Zeiger, um zu zählen, solange die linke Hälfte noch gültige Elemente enthält), und führen Sie anschließend wie gewohnt zusammen. Gesamtlaufzeit: 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])) # 3Globale gegenüber lokalen Inversionen
Globale und lokale Inversionen (LeetCode 775): Bei einer Permutation von 0..n-1 soll bestimmt werden, ob die Anzahl globaler Inversionen (aller Paare i<j mit a[i]>a[j]) der Anzahl lokaler Inversionen (benachbarter Paare) entspricht. Die zentrale Erkenntnis: Jede lokale Inversion ist auch eine globale, daher gilt global ≥ lokal. Beide Anzahlen sind genau dann gleich, wenn es keine nicht benachbarten Inversionen gibt – also kein Element mehr als eine Position von seinem sortierten Index entfernt ist. Damit genügt es, für alle i abs(a[i] - i) ≤ 1 zu prüfen.
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]Zusammenfassung der Komplexität der Inversionszählung
Zusammenfassung: Das Zählen von Inversionen per Brute Force hat eine Laufzeit von O(n²). Ein modifizierter Merge Sort erreicht O(n log n), indem während des Merge-Schritts Inversionen über die Teilungsgrenze hinweg gezählt werden. Der zusätzliche Aufwand beträgt pro Vergleich O(1) (durch die Addition von len(left) - i), daher beträgt der gesamte Zusatzaufwand pro Merge-Ebene O(n) – genauso wie beim standardmäßigen Merge Sort. Der Speicherbedarf für die Hilfsarrays beträgt O(n). Dies ist das klassische Beispiel dafür, wie sich mit Teile und Herrsche Rangstatistiken in logarithmisch-linearer Zeit zählen lassen.
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')Schnelltest
Überprüfen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep, die in dieser Lektion behandelt wurden.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: Inversionen messen, wie unsortiert ein Array ist, wobei Brute Force O(n²) und Teile und Herrsche O(n log n) benötigen, der modifizierte Merge Sort Inversionen über die beiden Hälften hinweg zählt, indem jedes Mal len(left)-i addiert wird, wenn ein Element aus der rechten Hälfte vor einem Element aus der linken Hälfte gewählt wird, und die Korrektheit auf der Aufteilung beruht: Inversionen innerhalb der linken Hälfte, innerhalb der rechten Hälfte und über die Hälften hinweg sind disjunkt und zusammen decken sie alle Inversionen ab. Als Nächstes betrachten wir den Boyer-Moore-Abstimmungsalgorithmus zum Finden des Mehrheitselements.
Häufig gestellte Fragen
Ist die Lektion „Inversionen mit modifiziertem Merge Sort zählen“ kostenlos?
Ja — der vollständige Text von „Inversionen mit modifiziertem Merge Sort zählen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Inversionen mit modifiziertem Merge Sort zählen“?
Zählen Sie die Inversionen eines Arrays – Paare, für die a[i] > a[j] und i < j gilt –, indem Sie während des Merge-Schritts die Inversionen zwischen den Teilarrays zählen. Du übst DSA Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um DSA Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. DSA Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 2 von 4.
Wie lange dauert die Lektion „Inversionen mit modifiziertem Merge Sort zählen“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser DSA Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede DSA Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Divide-and-Conquer-Vorlage
- Inversionen mit modifiziertem Merge Sort zählen
- Majority Element: Boyer-Moore-Abstimmung
- Median zweier sortierter Arrays