Menghitung Inversi Menggunakan Merge Sort Termodifikasi
Hitung jumlah inversi dalam sebuah array—pasangan dengan a[i] > a[j] dan i < j—dengan menghitung inversi lintas-pemisahan selama langkah penggabungan
Menghitung Inversi Menggunakan Merge Sort Termodifikasi adalah pelajaran DSA Interview Prep gratis di CoddyKit. Ini adalah pelajaran 2 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar DSA Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Apa Itu Inversi?
Inversi dalam sebuah larik adalah pasangan indeks (i, j) dengan i < j, tetapi a[i] > a[j] — elemen yang lebih besar muncul sebelum elemen yang lebih kecil. Sebagai contoh, dalam [3, 1, 2], inversinya adalah (3,1) dan (3,2), sehingga terdapat 2 inversi. Larik terurut memiliki 0 inversi. Larik yang terurut terbalik dengan n elemen memiliki n(n-1)/2 inversi. Penghitungan inversi mengukur seberapa jauh sebuah larik dari urutan terurut.
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]Pendekatan Naif O(n²)
Pendekatan dengan mencoba semua kemungkinan memeriksa seluruh pasangan (i, j) dengan i < j dan menghitung pasangan yang memenuhi a[i] > a[j]. Pendekatan ini membutuhkan waktu O(n²) dan ruang O(1). Untuk n = 10⁵, ini berarti 5 × 10⁹ perbandingan — terlalu lambat. Pendekatan Pecah dan Taklukkan menggunakan pengurutan merge yang dimodifikasi menyelesaikannya dalam O(n log n). Gagasan utamanya adalah bahwa selama langkah merge pada pengurutan merge, kita dapat menghitung inversi lintas pembagian secara efisien.
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])) # 3Wawasan Pengurutan Merge
Selama penggabungan dua paruh terurut L dan R, jika kita memilih elemen R[j] daripada L[i] (karena R[j] < L[i]), maka semua elemen yang tersisa dalam L mulai dari indeks i juga lebih besar daripada R[j]. Hal ini karena L sudah terurut. Jadi, setiap kali kita mengambil elemen dari paruh kanan, kita menghitung len(L) - i inversi lintas paruh. Penghitungan ini tidak memerlukan biaya tambahan — prosesnya berlangsung selama penggabungan biasa.
# 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')Implementasi Pengurutan Merge yang Dimodifikasi
Modifikasi pengurutan merge agar mengembalikan larik terurut dan jumlah inversi. Total inversi = inversi paruh kiri + inversi paruh kanan + inversi lintas paruh yang ditemukan selama penggabungan. Kasus dasar mengembalikan (satu elemen, 0 inversi). Fungsi merge menghitung inversi saat melakukan penggabungan. Waktu 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])) # 3Menelusuri Algoritma
Telusuri [2, 4, 1, 3]: bagi menjadi [2, 4] dan [1, 3]. Pengurutan sublarik kiri: [2, 4] → terurut [2,4], 0 inversi. Pengurutan sublarik kanan: [1, 3] → terurut [1,3], 0 inversi. Gabungkan [2,4] dan [1,3]: ambil 1 (count += 2 untuk 2>1 dan 4>1), ambil 2 (tidak ada penambahan), ambil 3 (count += 1 untuk 4>3), lalu ambil 4. Inversi lintas paruh = 3. Total = 0+0+3 = 3. Verifikasi: pasangan (2,1), (4,1), (4,3) = 3 inversi. ✓
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]))Mengapa Inversi Lintas Paruh Terhitung dengan Benar
Kebenaran: setiap pasangan inversi (a[i], a[j]) dengan i < j termasuk tepat dalam salah satu dari tiga kategori berikut: (1) Keduanya berada di paruh kiri — dihitung oleh pemanggilan rekursif kiri. (2) Keduanya berada di paruh kanan — dihitung oleh pemanggilan rekursif kanan. (3) Elemen paruh kiri > elemen paruh kanan — dihitung selama penggabungan sebagai inversi lintas paruh. Kategori-kategori ini saling eksklusif dan mencakup semua kemungkinan, sehingga tidak ada inversi yang dihitung dua kali atau terlewat. Argumen pembagian ini merupakan pembuktian kebenaran P&T yang umum.
# 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!')Penerapan Jumlah Inversi
Inversi mengukur keterurutan. Penerapannya: (1) Korelasi peringkat: jarak Kendall tau antara dua daftar berperingkat adalah jumlah inversi. (2) Efisiensi pengurutan penyisipan: pengurutan penyisipan melakukan swap tepat sebanyak jumlah inversi. (3) Analisis pengurutan gelembung: setiap lintasan pengurutan gelembung mengurangi jumlah inversi; jumlah lintasan yang diperlukan sama dengan jumlah inversi. (4) Keterpecahan teka-teki: teka-teki 8 atau 15 dapat diselesaikan jika dan hanya jika jumlah inversinya memiliki paritas tertentu.
# 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 disagreementTerkait: Menghitung Bilangan yang Lebih Kecil Setelah Elemen Ini
Count Smaller Numbers After Self (LeetCode 315) menanyakan untuk setiap elemen: berapa banyak elemen yang lebih kecil di sebelah kanannya? Ini adalah penghitungan inversi per elemen. Masalah ini dapat diselesaikan dengan pengurutan merge yang dimodifikasi, sambil melacak indeks asli yang dihitung. Alternatifnya, gunakan Pohon Berindeks Biner (Pohon Fenwick) atau pengurutan merge dengan pelacakan indeks. Pendekatan P&T berjalan dalam 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]Pasangan Terbalik
Pasangan Terbalik (LeetCode 493) menghitung pasangan (i, j) dengan i < j dan nums[i] > 2 × nums[j]. Penghitungan inversi standar menggunakan nums[i] > nums[j]. Di sini, batasnya berubah menjadi 2 × nums[j]. Modifikasi pengurutan merge: hitung pasangan lintas pembagian sebelum penggabungan (gunakan dua penunjuk untuk menghitung selama paruh kiri masih memiliki elemen yang valid), lalu lakukan penggabungan seperti biasa. Total waktu 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])) # 3Perbandingan Jumlah Inversi Global dan Lokal
Inversi Global dan Lokal (LeetCode 775): diberikan sebuah permutasi 0..n-1, tentukan apakah jumlah inversi global (semua pasangan i<j dengan a[i]>a[j]) sama dengan jumlah inversi lokal (pasangan yang bersebelahan). Inti pentingnya: setiap inversi lokal juga merupakan inversi global, sehingga inversi global ≥ inversi lokal. Keduanya sama jika dan hanya jika tidak ada inversi yang tidak bersebelahan—artinya, tidak ada elemen yang berjarak lebih dari 1 posisi dari indeksnya dalam larik terurut. Ini dapat disederhanakan menjadi pemeriksaan abs(a[i] - i) ≤ 1 untuk setiap 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]Ringkasan Kompleksitas Jumlah Inversi
Ringkasan: Penghitungan inversi dengan mencoba semua pasangan memiliki kompleksitas O(n²). Pengurutan gabung yang dimodifikasi mencapai O(n log n) dengan menghitung inversi lintas pemisahan selama tahap penggabungan. Biaya tambahannya adalah O(1) per perbandingan (menambahkan len(left) - i), sehingga total tambahan biayanya adalah O(n) pada setiap tingkat penggabungan—sama seperti pengurutan gabung standar. Ruang yang digunakan adalah O(n) untuk larik bantu. Ini merupakan contoh klasik penggunaan pendekatan bagi dan taklukkan untuk menghitung statistik urutan dalam waktu log-linear.
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')Pemeriksaan Singkat
Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Ringkasan Pelajaran
Dalam pelajaran ini Anda mempelajari: inversi mengukur seberapa tidak terurutnya sebuah larik, dengan pendekatan mencoba semua pasangan O(n²) dan pendekatan bagi dan taklukkan O(n log n), pengurutan gabung yang dimodifikasi menghitung inversi lintas bagian dengan menambahkan len(left)-i setiap kali elemen kanan dipilih daripada elemen kiri, dan kebenarannya bergantung pada pembagian: inversi kiri-kiri, kanan-kanan, dan lintas bagian saling terpisah dan bersama-sama mencakup semua inversi. Selanjutnya, kita membahas algoritma pemungutan suara Boyer-Moore untuk menemukan elemen mayoritas.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Menghitung Inversi Menggunakan Merge Sort Termodifikasi” gratis?
Ya — teks lengkap “Menghitung Inversi Menggunakan Merge Sort Termodifikasi” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus DSA Interview Prep, upgrade ke CoddyKit PRO. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Menghitung Inversi Menggunakan Merge Sort Termodifikasi”?
Hitung jumlah inversi dalam sebuah array—pasangan dengan a[i] > a[j] dan i < j—dengan menghitung inversi lintas-pemisahan selama langkah penggabungan Kamu berlatih DSA Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai DSA Interview Prep?
Tidak diperlukan pengalaman sebelumnya. DSA Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 2 dari 4.
Berapa lama pelajaran “Menghitung Inversi Menggunakan Merge Sort Termodifikasi” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran DSA Interview Prep ini?
Ya. Setiap pelajaran DSA Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Templat Divide and Conquer
- Menghitung Inversi Menggunakan Merge Sort Termodifikasi
- Elemen Mayoritas: Pemungutan Suara Boyer-Moore
- Median dari Dua Array Terurut