排序网络

· · 算法·理论

排序网络是一种非自适应的排序模型。

对于任意输入数据,算法执行的比较操作的位置和顺序都是不变的。因此,排序网络执行的流程没有控制语句,只有比较与交换。

一个排序网络仅由两种基本元件构成:

定理(01 原理)如果一个排序网络对于仅由 0 和 1 组成的序列可以排好序,那么它就能把任何实数序列正确排序。

证明 任取阈值 k,将 \le k 的数视作 0,>k 的数视作 1。反证,若其不能正确排序,则必有 1 在 0 前,与前提矛盾,故任意输入均可正确排序。

双调排序

定义 a 是双调序列,当且仅当:

考虑分治。假定 n 是 2 的幂,将序列从中点处劈开,对两个序列对位调用比较器,效果等价于对位取 \min 和 \max。

可以证明,两部分均为双调序列,且左侧不超过右侧。由 01 原理容易论证正确性。递归处理左右部分即可将双调序列排序。

只要令 a 成为双调序列再使用分治算法。双调化的方法是,将序列划分为两半分别排序,然后将右半翻转。

比较器数目 O(n \log^2 n)。

:::::info[代码]

void merge(int l, int r) {
    if (l == r) return;
    int mid = (l + r) >> 1;
    for (int i = l; i <= mid; i++) C(i, mid+1+i-l);
    merge(l, mid), merge(mid+1, r);
}
void solve(int l, int r) {
    if (l == r) return;
    int mid = (l + r) >> 1;
    solve(l, mid), solve(mid + 1, r);
    reverse(a + mid + 1, a + r + 1);
    merge(l, r);
}

:::::

奇偶排序

假定 n 是 2 的幂。考虑分治,只要归并不降序列 a_i,b_i。将 a,b 按下标奇偶分组,奇偶两组递归合并,对相邻奇偶位加一层比较器即可。

比较器数目 O(n \log^2 n)。

:::::info[代码]

void merge(int l, int r, int k) {
    int n = r - l + 1, m = 2 * k;
    if (m < n) {
        merge(l, r, m), merge(l+k, r+k, m);
        for (int i = l+k; i+k <= r; i += m) C(i, i+k);
    } else {
        C(l, l+k);
    }
}
void solve(int l, int r) {
    if (l == r) return;
    int mid = (l + r) >> 1;
    solve(l, mid), solve(mid + 1, r);
    merge(l, r, 1);
}

:::::

P8126 [BalticOI 2021] The Collection Game (Day2)

CF1552G A Serious Referee

初始有序列 a_1 \sim a_n。给定下述排序算法:执行 k 轮操作,第 i 轮对子序列 j_{i,1},j_{i,2},\cdots,j_{i,q_i} 排序。

判定对任意整数序列 a,算法能否正确排序。

:::::success[题解]

根据排序网络的 01 原理,算法正确性等价于对任意 01 序列正确排序。直接枚举 01 串可以做到 O(nk2^n)。

设第 i 次操作覆盖下标集合 S_i,显然 \left|\bigcup \limits_{i=1}^k S_i\right| \le n-2 无解。考虑爆搜,则第 i 层已知 01 分布的位置为 T_i=\bigcup \limits_{j=1}^{i-1} S_j。只要关心 S_i \setminus T_i 中 1 的数目,就能确定 T_{i+1}=S_i \cup T_i 的 01 分布情况。搜完 k 层后判定 01 分布是否为 00 \cdots 0 11 \cdots 1。

我们枚举 1 的数目,设 a_i=|S_i \setminus T_i| 则搜索节点数 \prod\limits_{i=1}^k (a_i+1),其中 \sum \limits_{i=1}^k a_i \le n。a_i 全相等最劣,时间代价 \left(\dfrac{n}{k}+1\right)^k \approx 9.7 \times 10^6。复杂度再乘上 \text{poly}(n,k)。

注意精细实现,使用二进制状压优化后可以通过。

:::::

:::::info[代码]

int n, k; u64 S[20];

bool dfs(int i, u64 T, u64 A) {
    if (i == k+1) {
        bool f1 = 0; int p = -1;
        for (int j = 0; j < n; j++) {
            if (!(T >> j & 1)) {
                p = j; continue;
            }
            if (A >> j & 1) f1 = 1;
            else if (f1) return false;
        }
        if (p == -1) return true;
        if (p > 0 && (A >> (p-1) & 1)) return false;
        if (p < n-1 && !(A >> (p+1) & 1)) return false;
        return true; 
    }
    int c0 = popcount(S[i] & T & ~A);
    int m = popcount(S[i] & ~T);
    for (int c = 0; c <= m; c++) {
        u64 A2 = A & T & ~S[i], x = S[i];
        int k = c + c0; 
        if (popcount(x) > k) {
            while (k--) x &= x - 1;
            A2 |= x;
        }
        if (!dfs(i + 1, T | S[i], A2)) return false;
    } return true;
}

void _main() {
    cin >> n >> k;
    u64 U = 0;
    for (int i = 1, m; i <= k; i++) {
        cin >> m;
        for (int x; m--; ) cin >> x, S[i] |= 1ULL << (x - 1);
        U |= S[i];
    }
    if (popcount(U) <= n-2) return cout << "REJECTED", void();
    cout << (dfs(1, 0, 0) ? "ACCEPTED" : "REJECTED");
}

:::::