Değiştirilmiş Birleştirmeli Sıralamayla Terslikleri Sayma
Bir dizideki tersliklerin sayısını — a[i] > a[j] ve i < j olan çiftleri — birleştirme adımında bölümler arası terslikleri sayarak bulun.
Değiştirilmiş Birleştirmeli Sıralamayla Terslikleri Sayma, CoddyKit'te ücretsiz bir DSA Interview Prep dersidir. Bu, 4 dersinin 2. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, DSA Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. DSA Interview Prep kursu toplamda 4 dersten oluşur.
İnversiyon Nedir?
Bir dizideki inversiyon, i < j olmasına rağmen a[i] > a[j] koşulunu sağlayan (i, j) indis çiftidir; yani daha büyük bir öğe daha küçük bir öğeden önce gelir. Örneğin [3, 1, 2] dizisindeki inversiyonlar (3,1) ve (3,2) olduğundan toplam 2 inversiyon vardır. Sıralı bir dizide 0 inversiyon bulunur. n öğeli ters sıralı bir dizide n(n-1)/2 inversiyon bulunur. İnversiyonları saymak, bir dizinin sıralı düzenden ne kadar uzak olduğunu ölçer.
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]Naif O(n²) Yaklaşım
Kaba kuvvet yaklaşımı, i < j koşulunu sağlayan tüm (i, j) çiftlerini kontrol eder ve a[i] > a[j] olanları sayar. Bu yaklaşım O(n²) zaman ve O(1) alan kullanır. n = 10⁵ için bu, 5 × 10⁹ karşılaştırma anlamına gelir; bu da çok yavaştır. Değiştirilmiş merge sıralamasını kullanan Böl ve Yönet yaklaşımı problemi O(n log n) içinde çözer. Temel fikir, merge sıralamasının birleştirme adımı sırasında bölmeler arası inversiyonları verimli biçimde sayabilmemizdir.
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])) # 3Merge Sıralamasından Çıkan İçgörü
L ve R adlı iki sıralı yarıyı birleştirirken, R[j] öğesini L[i] yerine seçersek (çünkü R[j] < L[i]), i indisinden itibaren L içindeki kalan tüm öğeler de R[j] öğesinden büyük olur. Bunun nedeni L'nin sıralı olmasıdır. Bu nedenle sağ yarıdan her öğe aldığımızda, len(L) - i kadar bölmeler arası inversiyon sayarız. Bu sayım ek bir maliyet oluşturmaz; normal birleştirme sırasında gerçekleşir.
# 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')Değiştirilmiş Merge Sıralaması Uygulaması
Merge sıralamasını, hem sıralanmış diziyi hem de inversiyon sayısını döndürecek şekilde değiştirin. Toplam inversiyon sayısı = sol yarıdaki inversiyonlar + sağ yarıdaki inversiyonlar + birleştirme sırasında bulunan bölmeler arası inversiyonlar. Taban durumu (tek öğe, 0 inversiyon) döndürür. Birleştirme işlevi, birleştirme sırasında inversiyonları sayar. Toplam zaman: 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])) # 3Algoritmanın İzini Sürme
[2, 4, 1, 3] dizisini izleyin: [2, 4] ve [1, 3] olarak bölün. Sol alt sıralama: [2, 4] → sıralı [2,4], 0 inversiyon. Sağ alt sıralama: [1, 3] → sıralı [1,3], 0 inversiyon. [2,4] ve [1,3] dizilerini birleştirin: 1'i alın (2>1 ve 4>1 için count += 2), 2'yi alın (sayım yok), 3'ü alın (4>3 için count += 1), ardından 4'ü alın. Bölmeler arası inversiyon sayısı = 3. Toplam = 0+0+3 = 3. Doğrulama: (2,1), (4,1), (4,3) çiftleri = 3 inversiyon. ✓
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]))Bölmeler Arası İnversiyonların Doğru Biçimde Yakalanmasının Nedeni
Doğruluk: i < j koşulunu sağlayan herhangi bir (a[i], a[j]) inversiyon çifti tam olarak şu üç kategoriden birine aittir: (1) İkisi de sol yarıdadır; sol özyinelemeli çağrı tarafından sayılır. (2) İkisi de sağ yarıdadır; sağ özyinelemeli çağrı tarafından sayılır. (3) Sol yarıdaki öğe, sağ yarıdaki öğeden büyüktür; birleştirme sırasında bölmeler arası inversiyon olarak sayılır. Kategoriler birbirini dışlar ve tüm durumları kapsar; bu nedenle hiçbir inversiyon iki kez sayılmaz veya atlanmaz. Bu bölümlendirme argümanı, Böl ve Yönet doğruluğunun standart kanıtıdır.
# 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!')İnversiyon Sayısının Uygulamaları
İnversiyonlar sıralılık derecesini ölçer. Uygulamaları: (1) Sıralama korelasyonu: İki sıralı liste arasındaki Kendall tau uzaklığı, inversiyonların sayısına eşittir. (2) Eklemeli sıralamanın verimliliği: Eklemeli sıralama, tam olarak inversiyon sayısı kadar yer değiştirme yapar. (3) Kabarcık sıralaması analizi: Her kabarcık sıralaması geçişi inversiyonları azaltır; gereken geçiş sayısı inversiyon sayısına eşittir. (4) Bulmacanın çözülebilirliği: Bir 8'li veya 15'li bulmaca, ancak ve ancak inversiyon sayısının belirli bir paritesi varsa çözülebilir.
# 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 disagreementİlgili: Kendinden Sonra Gelen Daha Küçük Sayıları Sayma
Kendinden Sonra Gelen Daha Küçük Sayıları Sayma (LeetCode 315), her öğe için sağında kaç tane daha küçük öğe olduğunu sorar. Bu, öğe başına inversiyon sayımıdır. Aynı değiştirilmiş merge sıralamasıyla, hangi özgün indislerin sayıldığını izleyerek çözülebilir. Alternatif olarak İkili İndeksli Ağaç (Fenwick Ağacı) veya indis takibi yapan bir merge sıralaması kullanılabilir. Böl ve Yönet yaklaşımı O(n log n) zamanda çalışır.
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]Ters Çiftler
Ters Çiftler (LeetCode 493), (i, j) koşulunda i < j ve nums[i] > 2 × nums[j] olan çiftleri sayar. Standart inversiyon sayımı nums[i] > nums[j] koşulunu kullanır. Burada eşik 2 × nums[j] olarak değişir. Merge sıralamasını değiştirin: birleştirmeden önce bölmeler arasını sayın (sol yarıda hâlâ geçerli öğeler varken saymak için iki işaretçi kullanın), ardından normal biçimde birleştirin. Toplam zaman 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])) # 3Genel Terslik Sayısı ve Yerel Terslikler
Genel ve Yerel Terslikler (LeetCode 775): 0..n-1 permütasyonu verildiğinde, genel tersliklerin (i<j ve a[i]>a[j] olan tüm çiftler) sayısının yerel tersliklerin (bitişik çiftler) sayısına eşit olup olmadığını belirleyiniz. Temel fikir: her yerel terslik aynı zamanda geneldir; dolayısıyla genel ≥ yerel olur. Bunlar ancak bitişik olmayan hiç terslik yoksa eşittir — yani hiçbir öğe sıralanmış dizisindeki indeksinden 1'den fazla uzak değildir. Bu da tüm i değerleri için abs(a[i] - i) ≤ 1 kontrolüne indirgenir.
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]Terslik Sayısı Karmaşıklığı Özeti
Özet: Kaba kuvvetle terslik sayımı O(n²)'dir. Değiştirilmiş birleştirmeli sıralama, birleştirme adımı sırasında bölümler arası terslikleri sayarak O(n log n) başarır. Ek maliyet, her karşılaştırma için O(1)'dir (len(left) - i eklenir); dolayısıyla her birleştirme düzeyindeki toplam ek yük — standart birleştirmeli sıralamayla aynı şekilde — O(n)'dir. Yardımcı diziler için alan O(n)'dir. Bu, doğrusal-logaritmik zamanda sıra istatistiklerini saymak için böl ve yönet yaklaşımının kullanılmasının klasik örneğidir.
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')Hızlı Kontrol
Bu dersteki Veri Yapıları ve Algoritmalar — Kodlama Mülakatı Hazırlığı kavramlarını ne kadar anladığınızı sınayınız.
Ders Özeti
Bu derste şunları öğrendiniz: terslikler bir dizinin ne kadar sırasız olduğunu ölçer; kaba kuvvet O(n²), böl ve yönet ise O(n log n) kullanır, değiştirilmiş birleştirmeli sıralama, bir sol öğe yerine sağ öğe her seçildiğinde len(left)-i ekleyerek iki yarı arasındaki terslikleri sayar ve doğruluk, bölümlemeye dayanır: sol-sol, sağ-sağ ve çapraz terslikler birbirini dışlar ve birlikte tüm terslikleri kapsar. Sırada, çoğunluk öğesini bulmak için Boyer-Moore oylama algoritmasını inceleyeceğiz.
Sıkça Sorulan Sorular
“Değiştirilmiş Birleştirmeli Sıralamayla Terslikleri Sayma” dersi ücretsiz mi?
Evet — “Değiştirilmiş Birleştirmeli Sıralamayla Terslikleri Sayma” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve DSA Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. DSA Interview Prep kursu toplamda 4 dersten oluşur.
“Değiştirilmiş Birleştirmeli Sıralamayla Terslikleri Sayma” dersinde ne öğreneceğim?
Bir dizideki tersliklerin sayısını — a[i] > a[j] ve i < j olan çiftleri — birleştirme adımında bölümler arası terslikleri sayarak bulun. DSA Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
DSA Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te DSA Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 2. dersidir.
“Değiştirilmiş Birleştirmeli Sıralamayla Terslikleri Sayma” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu DSA Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her DSA Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- Böl ve Yönet Şablonu
- Değiştirilmiş Birleştirmeli Sıralamayla Terslikleri Sayma
- Çoğunluk Öğesi: Boyer-Moore Oylaması
- İki Sıralı Dizinin Ortancası