排序网络
stripe_python · · 算法·理论
排序网络是一种非自适应的排序模型。
对于任意输入数据,算法执行的比较操作的位置和顺序都是不变的。因此,排序网络执行的流程没有控制语句,只有比较与交换。
一个排序网络仅由两种基本元件构成:
- 线:有
n 根水平线,代表需要排序的n 个元素,数据从左到右流动。 - 比较器:连接水平线
i 和j 的垂直线段。当元素经过比较器时,元素较小的会被放到上面的线,较大的则被放到下面的线。相当于下述代码:void C(int i, int j) { if (a[i] > a[j]) swap(a[i], a[j]); }
定理(01 原理)如果一个排序网络对于仅由
证明 任取阈值
双调排序
定义
考虑分治。假定
可以证明,两部分均为双调序列,且左侧不超过右侧。由 01 原理容易论证正确性。递归处理左右部分即可将双调序列排序。
只要令
比较器数目
:::::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);
}
:::::
奇偶排序
假定
比较器数目
:::::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 串可以做到
设第
我们枚举
注意精细实现,使用二进制状压优化后可以通过。
:::::
:::::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");
}
:::::