Inversies tellen met aangepaste merge sort
Tel het aantal inversies in een array — paren waarvoor a[i] > a[j] en i < j — door inversies over de splitsing heen te tellen tijdens de merge-stap.
Inversies tellen met aangepaste merge sort is een gratis Voorbereiding op programmeerinterviews-les op CoddyKit. Dit is les 2 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Voorbereiding op programmeerinterviews. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat is een inversie?
Een inversie in een array is een paar indices (i, j) waarvoor i < j, maar a[i] > a[j] — een groter element staat vóór een kleiner element. In [3, 1, 2] zijn de inversies bijvoorbeeld (3,1) en (3,2), dus zijn er 2 inversies. Een gesorteerde array heeft 0 inversies. Een array van n elementen die in omgekeerde volgorde is gesorteerd, heeft n(n-1)/2 inversies. Het tellen van inversies meet hoe ver een array van een gesorteerde volgorde afstaat.
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]Naïeve O(n²)-aanpak
De uitputtende aanpak controleert alle paren (i, j) met i < j en telt de paren waarvoor a[i] > a[j] geldt. Dit kost O(n²)-tijd en O(1)-ruimte. Voor n = 10⁵ betekent dit 5 × 10⁹ vergelijkingen — veel te traag. De verdeel-en-heersaanpak met een aangepaste mergesort lost dit op in O(n log n). Het belangrijkste inzicht is dat we tijdens het samenvoegen van mergesort kruisinversies efficiënt kunnen tellen.
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])) # 3Het inzicht achter mergesort
Tijdens het samenvoegen van twee gesorteerde helften L en R: als we element R[j] kiezen in plaats van L[i] (omdat R[j] < L[i]), zijn alle resterende elementen in L vanaf index i ook groter dan R[j]. Dat komt doordat L gesorteerd is. Elke keer dat we een element uit de rechterhelft nemen, tellen we daarom len(L) - i kruisinversies. Deze telling kost niets extra's — ze vindt plaats tijdens het normale samenvoegen.
# 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')Implementatie van aangepaste mergesort
Pas mergesort aan zodat deze zowel de gesorteerde array als de inversietelling retourneert. Het totale aantal inversies = inversies in de linkerhelft + inversies in de rechterhelft + kruisinversies die tijdens het samenvoegen zijn gevonden. Het basisgeval retourneert (één element, 0 inversies). De mergefunctie telt inversies terwijl ze de elementen samenvoegt. Totale tijd: 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])) # 3Het algoritme traceren
Traceer [2, 4, 1, 3]: splits op in [2, 4] en [1, 3]. Linker deel: [2, 4] → gesorteerd [2,4], 0 inversies. Rechter deel: [1, 3] → gesorteerd [1,3], 0 inversies. Voeg [2,4] en [1,3] samen: neem 1 (count += 2 voor 2>1 en 4>1), neem 2 (geen telling), neem 3 (count += 1 voor 4>3) en neem 4. Kruisinversies = 3. Totaal = 0+0+3 = 3. Controleer dit: paren (2,1), (4,1), (4,3) = 3 inversies. ✓
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]))Waarom kruisinversies correct worden geteld
Correctheid: elk inversiepaar (a[i], a[j]) waarvoor i < j geldt, behoort precies tot één van drie categorieën: (1) Beide elementen staan in de linkerhelft — geteld door de recursieve aanroep voor links. (2) Beide elementen staan in de rechterhelft — geteld door de recursieve aanroep voor rechts. (3) Een element uit de linkerhelft is groter dan een element uit de rechterhelft — geteld tijdens het samenvoegen als kruisinversies. De categorieën sluiten elkaar uit en zijn volledig, dus geen enkele inversie wordt dubbel geteld of overgeslagen. Dit partitie-argument is het standaardbewijs van correctheid voor 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!')Toepassingen van inversietelling
Inversies meten de mate van sortering. Toepassingen: (1) Ranglijstcorrelatie: de Kendall-tau-afstand tussen twee gerangschikte lijsten is het aantal inversies. (2) Efficiëntie van insertion sort: insertion sort voert precies evenveel verwisselingen uit als er inversies zijn. (3) Analyse van bubble sort: elke doorgang van bubble sort vermindert het aantal inversies; het benodigde aantal doorgangen is gelijk aan het aantal inversies. (4) Oplosbaarheid van puzzels: een 8-puzzle of 15-puzzle is oplosbaar dan en slechts dan als het aantal inversies een specifieke pariteit heeft.
# 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 disagreementGerelateerd: kleinere getallen na zichzelf tellen
Kleinere getallen na zichzelf tellen (LeetCode 315) vraagt voor elk element: hoeveel elementen rechts ervan zijn kleiner? Dit is een inversietelling per element. Je kunt dit oplossen met dezelfde aangepaste mergesort, waarbij je bijhoudt welke oorspronkelijke indices worden geteld. Je kunt ook een Binary Indexed Tree (Fenwick Tree) of een mergesort met indexregistratie gebruiken. De D&C-aanpak werkt in 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]Omgekeerde paren
Omgekeerde paren (LeetCode 493) telt paren (i, j) waarvoor i < j en nums[i] > 2 × nums[j]. Bij de standaardinversietelling gebruiken we nums[i] > nums[j]. Hier verandert de drempel in 2 × nums[j]. Pas mergesort aan: tel de paren over de splitsing heen vóór het samenvoegen (gebruik twee aanwijzers om te tellen zolang de linkerhelft nog geldige elementen bevat) en voeg daarna de elementen normaal samen. In totaal 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 versus lokale inversietelling
Globale en lokale inversies (LeetCode 775): gegeven een permutatie van 0..n-1, bepaal je of het aantal globale inversies (alle paren i<j met a[i]>a[j]) gelijk is aan het aantal lokale inversies (aangrenzende paren). Het belangrijkste inzicht is dat elke lokale inversie ook globaal is, dus globaal ≥ lokaal. Ze zijn precies dan gelijk wanneer er geen niet-aangrenzende inversies zijn — dus wanneer geen enkel element meer dan 1 positie van zijn gesorteerde index af staat. Dit komt neer op controleren of voor alle i abs(a[i] - i) ≤ 1 geldt.
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]Samenvatting van de complexiteit van inversietelling
Samenvatting: inversies tellen met brute force kost O(n²). Aangepaste mergesort bereikt O(n log n) door tijdens de samenvoegstap inversies over de splitsing heen te tellen. De extra kosten bedragen O(1) per vergelijking (door len(left) - i op te tellen), dus de totale extra tijd is O(n) per samenvoegniveau — hetzelfde als bij standaard mergesort. De ruimtecomplexiteit is O(n) voor de hulparrays. Dit is het canonieke voorbeeld van het gebruik van verdeel en heers om rangstatistieken in lineair-logaritmische tijd te tellen.
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')Snelle controle
Test je begrip van de concepten uit Data Structures & Algorithms — Coding Interview Prep die in deze les aan bod kwamen.
Samenvatting van de les
In deze les heb je geleerd: inversies geven aan hoe ongesorteerd een array is, met brute force O(n²) en verdeel en heers O(n log n), de aangepaste mergesort telt inversies tussen helften door elke keer len(left)-i op te tellen wanneer een element uit rechts wordt gekozen boven een element uit links, en de juistheid steunt op de opsplitsing: inversies binnen links, binnen rechts en tussen beide helften sluiten elkaar uit en omvatten samen alle inversies. Hierna bekijken we het Boyer-Moore-stemalgoritme om het meerderheidselement te vinden.
Leer Voorbereiding op programmeerinterviews met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 90
- Lessen
- 360
Veelgestelde vragen
Is de les “Inversies tellen met aangepaste merge sort” gratis?
Ja — de volledige tekst van “Inversies tellen met aangepaste merge sort” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Voorbereiding op programmeerinterviews wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat leer ik in “Inversies tellen met aangepaste merge sort”?
Tel het aantal inversies in een array — paren waarvoor a[i] > a[j] en i < j — door inversies over de splitsing heen te tellen tijdens de merge-stap. Je oefent met Voorbereiding op programmeerinterviews door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Voorbereiding op programmeerinterviews te beginnen?
Ervaring vooraf is niet nodig. Voorbereiding op programmeerinterviews op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 2 van 4.
Hoe lang duurt de les “Inversies tellen met aangepaste merge sort”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Voorbereiding op programmeerinterviews?
Ja. Elke les over Voorbereiding op programmeerinterviews bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Divide-and-conquer-sjabloon
- Inversies tellen met aangepaste merge sort
- Meerderheidselement: Boyer-Moore-stemmen
- Mediaan van twee gesorteerde arrays