Zliczanie inwersji za pomocą zmodyfikowanego sortowania przez scalanie
Zliczać liczbę inwersji w tablicy — par, dla których a[i] > a[j] i i < j — zliczając inwersje między podziałami podczas etapu scalania
Zliczanie inwersji za pomocą zmodyfikowanego sortowania przez scalanie to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 2 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Czym jest inwersja?
Inwersja w tablicy to para indeksów (i, j), dla której i < j, ale a[i] > a[j] — większy element występuje przed mniejszym. Na przykład w tablicy [3, 1, 2] inwersje to (3,1) i (3,2), więc występują 2 inwersje. Posortowana tablica ma 0 inwersji. Tablica n elementów posortowana odwrotnie ma n(n-1)/2 inwersji. Zliczanie inwersji mierzy, jak bardzo tablica różni się od uporządkowania rosnącego.
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]Naiwne podejście O(n²)
Podejście brute force sprawdza wszystkie pary (i, j) z i < j i zlicza te, dla których a[i] > a[j]. Wymaga ono czasu O(n²) i pamięci O(1). Dla n = 10⁵ oznacza to 5 × 10⁹ porównań — zdecydowanie za dużo. Podejście dziel i zwyciężaj, wykorzystujące zmodyfikowane sortowanie przez scalanie, rozwiązuje ten problem w czasie O(n log n). Kluczowa obserwacja jest taka, że podczas etapu scalania w sortowaniu przez scalanie możemy efektywnie zliczać inwersje między częściami.
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])) # 3Wniosek wynikający z sortowania przez scalanie
Podczas scalania dwóch posortowanych połówek L i R, jeśli wybierzemy element R[j] zamiast L[i] (ponieważ R[j] < L[i]), to wszystkie pozostałe elementy w L od indeksu i wzwyż również są większe od R[j]. Wynika to z faktu, że L jest posortowana. Dlatego za każdym razem, gdy pobieramy element z prawej połowy, zliczamy len(L) - i inwersji między połowami. To zliczanie nic nie kosztuje — odbywa się podczas zwykłego scalania.
# 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')Implementacja zmodyfikowanego sortowania przez scalanie
Modyfikujemy sortowanie przez scalanie tak, aby zwracało zarówno posortowaną tablicę, jak i liczbę inwersji. Łączna liczba inwersji = inwersje w lewej połowie + inwersje w prawej połowie + inwersje między połowami znalezione podczas scalania. Przypadek bazowy zwraca (pojedynczy element, 0 inwersji). Funkcja scalająca zlicza inwersje podczas scalania. Łączny czas działania: 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])) # 3Śledzenie działania algorytmu
Prześledźmy [2, 4, 1, 3]: dzielimy tablicę na [2, 4] i [1, 3]. Sortowanie lewej części: [2, 4] → posortowane [2,4], 0 inwersji. Sortowanie prawej części: [1, 3] → posortowane [1,3], 0 inwersji. Scalanie [2,4] i [1,3]: pobieramy 1 (count += 2 dla 2>1 i 4>1), pobieramy 2 (bez zwiększania licznika), pobieramy 3 (count += 1 dla 4>3), a następnie 4. Inwersje między połowami = 3. Łącznie = 0+0+3 = 3. Weryfikacja: pary (2,1), (4,1), (4,3) = 3 inwersje. ✓
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]))Dlaczego inwersje między połowami są zliczane poprawnie
Poprawność: każda para inwersyjna (a[i], a[j]), dla której i < j, należy dokładnie do jednej z trzech kategorii: (1) Oba elementy znajdują się w lewej połowie — zlicza je rekurencyjne wywołanie dla lewej części. (2) Oba elementy znajdują się w prawej połowie — zlicza je rekurencyjne wywołanie dla prawej części. (3) Element z lewej połowy > element z prawej połowy — zliczamy je podczas scalania jako inwersje między połowami. Kategorie są rozłączne i wyczerpują wszystkie możliwości, więc żadna inwersja nie jest zliczana podwójnie ani pomijana. Ten argument oparty na podziale jest standardowym dowodem poprawności dla metody 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!')Zastosowania zliczania inwersji
Inwersje mierzą stopień uporządkowania. Zastosowania: (1) Korelacja rankingów: odległość tau Kendalla między dwiema listami rankingowymi jest równa liczbie inwersji. (2) Wydajność sortowania przez wstawianie: sortowanie przez wstawianie wykonuje dokładnie tyle zamian, ile jest inwersji. (3) Analiza sortowania bąbelkowego: każde przejście sortowania bąbelkowego zmniejsza liczbę inwersji; liczba potrzebnych przejść jest równa liczbie inwersji. (4) Rozwiązywanie łamigłówek: 8-puzzle lub 15-puzzle da się rozwiązać wtedy i tylko wtedy, gdy liczba inwersji ma określoną parzystość.
# 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 disagreementPowiązane: Count Smaller Numbers After Self
Count Smaller Numbers After Self (LeetCode 315) wymaga dla każdego elementu określenia, ile mniejszych elementów znajduje się na jego prawo. Jest to zliczanie inwersji dla każdego elementu. Problem można rozwiązać za pomocą tego samego zmodyfikowanego sortowania przez scalanie, śledząc oryginalne indeksy zliczanych elementów. Alternatywnie można użyć struktury Binary Indexed Tree (Fenwick Tree) albo sortowania przez scalanie ze śledzeniem indeksów. Podejście D&C działa w czasie 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]Pary odwrotne
Reverse Pairs (LeetCode 493) zlicza pary (i, j), dla których i < j oraz nums[i] > 2 × nums[j]. Standardowe zliczanie inwersji wykorzystuje warunek nums[i] > nums[j]. Tutaj próg zmienia się na 2 × nums[j]. Należy zmodyfikować sortowanie przez scalanie: zliczać elementy między podziałami przed scalaniem (użyć dwóch wskaźników, aby zliczać, dopóki lewa połowa nadal zawiera prawidłowe elementy), a następnie wykonać zwykłe scalanie. Łączna złożoność wynosi 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])) # 3Inwersje globalne a lokalne
Inwersje globalne i lokalne (LeetCode 775): dla permutacji liczb od 0 do n-1 należy określić, czy liczba inwersji globalnych (wszystkich par i<j, dla których a[i]>a[j]) jest równa liczbie inwersji lokalnych (par sąsiednich). Kluczowa obserwacja: każda inwersja lokalna jest również globalna, więc liczba globalnych ≥ lokalnych. Są one równe wtedy i tylko wtedy, gdy nie występują inwersje niesąsiednie — oznacza to, że żaden element nie znajduje się w odległości większej niż 1 od swojej pozycji w posortowanej tablicy. Sprowadza się to do sprawdzenia, czy dla każdego i zachodzi abs(a[i] - i) ≤ 1.
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]Podsumowanie złożoności obliczania liczby inwersji
Podsumowanie: naiwny algorytm zliczania inwersji ma złożoność O(n²). Zmodyfikowane sortowanie przez scalanie osiąga O(n log n), zliczając inwersje między podziałami podczas kroku scalania. Dodatkowy koszt to O(1) na porównanie (dodanie len(left) - i), więc całkowity narzut wynosi O(n) na każdy poziom scalania — tyle samo co w standardowym sortowaniu przez scalanie. Złożoność pamięciowa wynosi O(n) dla tablic pomocniczych. To kanoniczny przykład zastosowania D&C do zliczania statystyk pozycyjnych w czasie liniowo-logarytmicznym.
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')Szybki test
Sprawdź swoje zrozumienie zagadnień Data Structures & Algorithms — Coding Interview Prep omówionych w tej lekcji.
Podsumowanie lekcji
W tej lekcji poznali Państwo: inwersje mierzą, jak bardzo tablica jest nieposortowana; metoda brutalnej siły ma złożoność O(n²), a D&C — O(n log n), zmodyfikowane sortowanie przez scalanie zlicza inwersje między połówkami, dodając len(left)-i za każdym razem, gdy element z prawej połowy zostaje wybrany przed elementem z lewej, oraz poprawność opiera się na podziale: inwersje w lewej połowie, w prawej połowie i między połówkami są rozłączne i razem obejmują wszystkie inwersje. Następnie zajmiemy się algorytmem głosowania Boyera-Moore’a służącym do znajdowania elementu większościowego.
Często zadawane pytania
Czy lekcja „Zliczanie inwersji za pomocą zmodyfikowanego sortowania przez scalanie” jest bezpłatna?
Tak — pełny tekst „Zliczanie inwersji za pomocą zmodyfikowanego sortowania przez scalanie” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Zliczanie inwersji za pomocą zmodyfikowanego sortowania przez scalanie”?
Zliczać liczbę inwersji w tablicy — par, dla których a[i] > a[j] i i < j — zliczając inwersje między podziałami podczas etapu scalania Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 2 z 4.
Ile czasu zajmuje lekcja „Zliczanie inwersji za pomocą zmodyfikowanego sortowania przez scalanie”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Schemat dziel i zwyciężaj
- Zliczanie inwersji za pomocą zmodyfikowanego sortowania przez scalanie
- Element większościowy: głosowanie Boyera-Moore’a
- Mediana dwóch posortowanych tablic