Day 099-Q4 — Batcherのビトニックソートネットワーク（Sorting Network）

2026-07-22 赤色 Master / Phase 8+ ★★★★★★★★★ Batcher's Bitonic Sort

問題

長さ $N$ の数列 $a_1,\dots,a_N$ が与えられる（$N$ は2べき）。Batcherのビトニックソートネットワークを用いてこの数列を昇順に整列せよ。

ビトニックソートネットワークは「比較器（compare-exchange）」だけを固定の順序で並べた回路であり、入力の値によらず同じ比較器列を適用すれば必ずソートされる（並列ハードウェアでのソートに応用される）。

出力として (1) 使用した比較器の総数、(2) ソート後の数列、の2つを求めよ。

入力形式

N
a_1 a_2 ... a_N

制約

$N$ は2べき
$1 \le N \le 4096$
$-10^9 \le a_i \le 10^9$

入出力例

入力例1

4
5 3 8 1

出力例1

6
1 3 5 8

比較器の総数は $\frac{N}{4}\log_2 N(\log_2 N+1) = \frac{4}{4}\times2\times3=6$ と一致する。

概念図: N=4 のソーティングネットワーク配線図

N=4: 比較器6個の配線図（左から右へ時系列） w0 w1 w2 w3 5 (入力: w0=5,w1=3,w2=8,w3=1) 1 2 3 4 5 6 出力: 1,3,5,8（昇順）

ヒント（段階的開示）

ヒント1: 方向性
「ビトニック数列」（前半が単調増加、後半が単調減少になっている数列）は、特別な比較の仕方で$O(\log N)$段の比較器だけで完全にソートできる。任意の数列を2つのビトニック数列の半分ずつに分けて再帰処理し、最後に1回のビトニックマージで合体する構造を考えよ。
ヒント2: アプローチ
bitonic_sort(lo,cnt,dir)は前半を昇順・後半を降順に再帰ソートしてビトニック数列を作り、最後にbitonic_mergeで方向dirに整列する。bitonic_merge(lo,cnt,dir)は前半iと後半i+cnt/2を比較器でペアにし、その後前半・後半をそれぞれ再帰的にマージする。比較器総数は$T(N)=\frac{N}{4}\log_2N(\log_2N+1)$。
ヒント3: 誘導（コード骨格） 
def bitonic_merge(a, lo, cnt, direction):
    if cnt > 1:
        k = cnt // 2
        for i in range(lo, lo + k):
            compare_exchange(a, i, i + k, direction)
        bitonic_merge(a, lo, k, direction)
        bitonic_merge(a, lo + k, k, direction)

def bitonic_sort(a, lo, cnt, direction):
    if cnt > 1:
        k = cnt // 2
        bitonic_sort(a, lo, k, True)
        bitonic_sort(a, lo + k, k, False)
        bitonic_merge(a, lo, cnt, direction)

模範解答 (Python)

import sys


def solve():
    data = sys.stdin.read().split()
    n = int(data[0])
    a = [int(x) for x in data[1:1 + n]]

    ops = 0

    def compare_exchange(i, j, direction):
        nonlocal ops
        ops += 1
        if (a[i] > a[j]) == direction:
            a[i], a[j] = a[j], a[i]

    def bitonic_merge(lo, cnt, direction):
        if cnt > 1:
            k = cnt // 2
            for i in range(lo, lo + k):
                compare_exchange(i, i + k, direction)
            bitonic_merge(lo, k, direction)
            bitonic_merge(lo + k, k, direction)

    def bitonic_sort(lo, cnt, direction):
        if cnt > 1:
            k = cnt // 2
            bitonic_sort(lo, k, True)
            bitonic_sort(lo + k, k, False)
            bitonic_merge(lo, cnt, direction)

    bitonic_sort(0, n, True)

    print(ops)
    print(' '.join(map(str, a)))


solve()
計算量: 比較器総数 $T(N)=\frac{N}{4}\log_2N(\log_2N+1)=O(N\log^2N)$。データ依存分岐なしで並列実行可能。

Step-by-Step 解説

1ビトニック数列とは
単調増加後に単調減少する（あるいはその巡回シフト）数列。特別な比較の当て方で$O(\log N)$段だけで完全ソート可能。
2bitonic_mergeの仕組み
前半・後半を同じオフセットでペアにして比較器を当てると、両方が半分の長さのビトニック数列になり前半≤後半（または逆）が保証される（ビトニックマージ定理）。
3bitonic_sortの分割統治
前半を昇順・後半を降順に再帰ソートすると全体が1つのビトニック数列になり、あとはbitonic_mergeで目的方向に整列する。
4再帰の停止条件と比較器総数
cnt==1で停止。漸化式$T(N)=2T(N/2)+\frac{N}{2}\log_2N$を解くと$T(N)=\frac{N}{4}\log_2N(\log_2N+1)$。
5ソーティングネットワークとしての意義
比較する添字ペアが入力値に依存せず事前決定できる（データ非依存）ため、並列ハードウェアや秘密計算でのソートに応用される。

よくあるミス

ミス原因正しい書き方
前半・後半を両方昇順でソートビトニック数列にならずbitonic_mergeの前提が崩れる前半はTrue、後半はFalseで再帰する
$N$が2べきでない入力にそのまま適用分割が整数比で半分にならない$N$が2べきであることを前提とする（一般化は番兵挿入で対応）
比較器のカウントをbitonic_mergeの外側だけで数える再帰内部の比較器も数える必要があるcompare_exchangeの呼び出し自体でカウンタをインクリメントする
directionの引き継ぎを誤って固定にするbitonic_merge内の再帰呼び出しは同じdirectionを渡す設計再帰呼び出しでも同じdirectionをそのまま渡す

次のステップ

  • 発展: $N$が2べきでない場合の拡張（番兵挿入、または奇偶マージソートによる一般化）
  • 次回予告: Zobrist Hashing（盤面差分XORハッシュ・重複状態検出）

自己評価

自分の回答

気づき・メモ