Coding Interview Prep · レッスン

変更版マージソートで転倒数を数える

Q: Coding Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。

Q: 「変更版マージソートで転倒数を数える」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

Q: このCoding Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

配列内の転倒数（a[i] > a[j]かつi < jを満たす組）の個数を、マージ段階で分割をまたぐ転倒を数えることで求めます。

「変更版マージソートで転倒数を数える」はCoddyKit上の無料Coding Interview Prepレッスンです。これはレッスン2/4です。下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

転倒とは何か

配列における転倒とは、i < jでありながらa[i] > a[j]となるインデックスの組(i, j)です。つまり、大きな要素が小さな要素より前に現れます。例えば[3, 1, 2]では、転倒は(3,1)と(3,2)なので、転倒数は2です。ソート済み配列の転倒数は0です。n個の要素を逆順に並べた配列の転倒数はn(n-1)/2です。転倒数を数えることで、配列がソート済みの順序からどれだけ離れているかを測れます。

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]

素朴なO(n²)アプローチ

総当たりのアプローチでは、i < jを満たすすべての組(i, j)を調べ、a[i] > a[j]となる組を数えます。時間計算量はO(n²)、空間計算量はO(1)です。n = 10⁵の場合、これは5 × 10⁹回の比較を意味するため、遅すぎます。変更したマージソートを使う分割統治法なら、O(n log n)で解決できます。重要な洞察は、マージソートのマージ段階で、分割をまたぐ転倒を効率的に数えられることです。

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]))  # 3

マージソートから得られる洞察

ソート済みの2つの半分LとRをマージするとき、R[j] < L[i]であるためにL[i]よりR[j]を選んだ場合、Lのi以降に残っているすべての要素もR[j]より大きくなります。これはLがソート済みだからです。そのため、右半分から要素を取り出すたびに、分割をまたぐ転倒をlen(L) - i個数えます。この計数には追加の処理は必要ありません。通常のマージ処理の中で同時に行えます。

# 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')

変更したマージソートの実装

マージソートを変更し、ソート済み配列と転倒数の両方を返すようにします。転倒の合計 = 左半分の転倒数 + 右半分の転倒数 + マージ中に見つかった分割をまたぐ転倒数です。ベースケースでは、（1要素、転倒数0）を返します。マージ関数は、マージしながら転倒を数えます。全体の時間計算量は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

アルゴリズムを追跡する

[2, 4, 1, 3]を追跡してみましょう。[2, 4]と[1, 3]に分割します。左側のソートでは、[2, 4] → ソート後は[2,4]、転倒数は0です。右側のソートでは、[1, 3] → ソート後は[1,3]、転倒数は0です。[2,4]と[1,3]をマージします。1を取り出すと、2>1と4>1のためcount += 2となります。2を取り出してもcountは増えません。3を取り出すと、4>3のためcount += 1となります。最後に4を取り出します。分割をまたぐ転倒数は3です。合計は0+0+3 = 3です。確認すると、組(2,1)、(4,1)、(4,3)の3つが転倒です。✓

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]))

分割をまたぐ転倒を正しく数えられる理由

正しさを確認します。i < jを満たす任意の転倒の組(a[i], a[j])は、必ず次の3種類のいずれか1つに属します。(1) 両方が左半分にある — 左側の再帰呼び出しで数えます。(2) 両方が右半分にある — 右側の再帰呼び出しで数えます。(3) 左半分の要素が右半分の要素より大きい — マージ中に分割をまたぐ転倒として数えます。これらの分類は互いに排他的で、すべてのケースを網羅しているため、転倒が二重に数えられたり、数え漏れたりすることはありません。この分割による論証は、分割統治法の正しさを示す標準的な証明です。

# 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!')

転倒数の応用

転倒数はソートされている度合いを測ります。応用例は次のとおりです。(1) 順位相関: 2つの順位リスト間のKendallのτ距離は、転倒数です。(2) 挿入ソートの効率: 挿入ソートで行われる交換回数は、転倒数と正確に等しくなります。(3) バブルソートの分析: バブルソートの各パスは転倒数を減らし、必要なパス数は転倒数と等しくなります。(4) パズルの可解性: 8パズルや15パズルは、転倒数の偶奇性が特定の条件を満たす場合に限り解くことができます。

# 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

Reverse Pairs

Reverse Pairs（LeetCode 493）では、i < jかつnums[i] > 2 × nums[j]を満たす組(i, j)を数えます。通常の転倒数ではnums[i] > nums[j]を使いますが、ここではしきい値が2 × nums[j]に変わります。マージソートを変更し、マージする前に分割をまたぐ組を数えます（左半分に条件を満たす要素が残っている間、2ポインタで数えます）。その後、通常どおりマージします。全体の時間計算量は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])) # 3

グローバル転倒数と局所転倒数

グローバル転倒と局所転倒 (LeetCode 775): 0..n-1 の順列が与えられたとき、グローバル転倒（i<j かつ a[i]>a[j] を満たすすべての組）の数が、局所転倒（隣接する要素の組）の数と等しいか判定します。重要な点は、すべての局所転倒がグローバル転倒でもあるため、グローバル転倒数 ≥ 局所転倒数となることです。両者が等しくなるのは、非隣接転倒が存在しない場合、つまり、どの要素もソート後の位置から2以上離れていない場合に限ります。これは、すべての i について 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]

転倒数の計算量まとめ

まとめると、総当たりによる転倒数の計算量は O(n²) です。マージソートを改良すると、マージの過程で分割をまたぐ転倒を数えることにより O(n log n) を実現できます。追加コストは比較1回あたり O(1)（len(left) - i を加算）なので、各マージ段階でのオーバーヘッドは O(n) となり、標準的なマージソートと同じです。補助配列のため、空間計算量は O(n) です。これは、D&C を使って順序統計量を線形対数時間で数える典型的な例です。

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')

クイックチェック

このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念の理解度を確認しましょう。

レッスンのまとめ

このレッスンでは、転倒は配列がどれだけ未整列かを表し、総当たり法の計算量は O(n²)、D&C の計算量は O(n log n) であること、改良版マージソートでは、右側の要素が左側の要素より先に選ばれるたびに len(left)-i を加算することで、半分をまたぐ転倒を数えられること、そして正しさは分割による分類に基づいており、左側内、右側内、左右をまたぐ転倒が互いに重複せず、すべての転倒を網羅することを学びました。次は、過半数要素を見つける Boyer-Moore 投票アルゴリズムを扱います。

よくある質問