はじめに
バイトニックソートのWikiにこんな図が載っています。
バイトニックソートの証明の解説を書いたんですが：
ここでいう順コンパレータだけで構成されています。逆が無いのですべて昇順です。この形でバイトニックソートを実行する場合、どのような証明になるのかというのがテーマです。
内容的には、Wikiにもある通り、最後の統合時に下半分を逆にする...でいいんでしょうが、これを愚直に受け取ると、逆にしたまま最後まで行ってしまうんですね。それでも昇順にするという操作の効果が効いて、結局うまくソートできるんですが、モヤモヤが残ります。そこで自分としては、本家のバイトニックソートを証明するときと同じように、0-1原理に基づいて証明しようと思います。一部分変えるだけですし、大して難しくないので、これでやりたいです。きちんと証明できた方が安心ですからね。
なおこのやり方だと任意個数の場合にダミーを用意する必要が無く、インデックス比較で完結するので、いくつでもできます。最後にそういった例も紹介できればと思います。
証明の概要
まず、ソートは上の図にあるような形で実行します。すべて順コンパレータ、これを並べて作られているので、「ネットワーク」です。用語に関しては上記のQiitaに準拠します。
証明は同じで、バイナリ正当であることを示すことで証明とします。そこに関してはもう証明が終わっているのでやりません。入力が0と1のみからなる配列であるとして証明できれば終わりです。
たとえば上の図は16の場合ですが、8までの部分を見ると分かるように上下で同じことをしています。これらは共に昇順への並び替えです（当然ですが...全体も昇順で終わるので）。ですから通常のバイトニックソートと違って昇順・降順ではなく昇順・昇順という形で統合ステップに行くわけです。それでもうまくいくのはなぜか、というのがポイントとなります。
その際、こっちの証明で用意したバイトニック列に関する2つの補題がそのまま使えるので、これで証明できるという流れになります。
証明
いきなりこの図から証明を始めます。入力は0と1のみからなる配列とします。
まずこの図にあるような場合を考えるとし、8までは証明が終わっているとします。つまり赤い部分は昇順でソートが終わっています。まず、これの後半部分を逆順にします。
a_1,a_2,\cdots,a_n,~~a_{2n},a_{2n-1},\cdots,a_{n+1}.
こうすると昇順・降順の並びになるので、バイトニック列です。さて、この列に対して、0-1バイトニック列の補題（１）を適用するため、$b$と$c$を作ります。
b = (\min(a_i, a_{2n+1-i}))_{i=1}^n,~~~~c = (\max(a_i, a_{2n+1-i}))_{i=1}^n.
これらの$b,c$はいずれも0,1からなるバイトニック列で、$b$の最大値$\leq c$の最小値となっています。そうしたうえで、$c$だけ逆順にします。こうしたところで、バイトニック列であるという性質は保たれますし、最小値も不変です。
b = (\min(a_i, a_{2n+1-i}))_{i=1}^n,~~~~c = (\max(a_{n+1-i}, a_{n+i}))_{i=1}^n.
この$b,c$こそが最初のソートが終わった時の結果になっています。そしてこれらは共に0,1のみからなるバイトニック列で、$b$の最大値$\leq c$の最小値です。これ以降の処理は、すべて同じですから、0-1バイトニック列の補題（２）により、いずれも最終的に昇順となります。
それで帰納法のスタート地点ですが、これも同じですね。ですから、あとは数学的帰納法で証明が終わります。
実装の実際
実際に実装してみました。こちらになります：
function setup() {
createCanvas(512, 512);
const rArray = [];
const r0 = [];
for(let i=0; i<512; i++){
r0.push(random(512));
}
rArray.push(r0);
// ソートが完了したやつをぶちこんでいく
const createBitonic = (r, c) => {
const s = new Array(512);
// rをbitonicしてsにぶち込んで返す
for(let i=0; i<512; i++){
const other = i ^ c;
const selfValue = r[i];
const otherValue = r[other];
// 相方と大小を調べるだけなので簡便です。
if((i<other) ^ (selfValue < otherValue)){ s[i] = otherValue; }else{ s[i] = selfValue; }
}
return s;
}
const m = [];
for(let k=1; k<=9; k++){
for(let j=k-1; j>=0; j--){
// comparerはこんな感じ。
const comparer = (j===k-1 ? (1<<(j+1))-1 : (1<<j));
m.push(comparer);
}
}
for(let i=0; i<m.length; i++){
rArray.push(createBitonic(rArray[rArray.length-1], m[i]));
}
background(100,150,200);
noStroke();
colorMode(HSL,1,1,1);
const bandWidth = 512/rArray.length; // 11.13くらい
for(let i=0; i<rArray.length; i++){
const y = i*bandWidth;
for(let t=0; t<512; t++){
fill(0.05, 0.5, rArray[i][t]/512);
rect(t,y,1,bandWidth);
}
}
// check. sortに失敗していたらエラーが出る。
const result = rArray[rArray.length-1];
for(let i=0; i<511; i++){
if(result[i]>result[i+1]){ console.error("failure!"); break; }
}
}
例によって最後にチェックしています。エラーが出ないので、ソートされていますね。図を見ると分かりますが、すべての比較対象を求める操作は対称差（^）で表現できるので、それをあらかじめ計算しておくだけです。ここですね。
const createBitonic = (r, c) => {
const s = new Array(512);
// rをbitonicしてsにぶち込んで返す
for(let i=0; i<512; i++){
const other = i ^ c;
const selfValue = r[i];
const otherValue = r[other];
// 相方と大小を調べるだけなので簡便です。
if((i<other) ^ (selfValue < otherValue)){ s[i] = otherValue; }else{ s[i] = selfValue; }
}
return s;
}
const m = [];
for(let k=1; k<=9; k++){
for(let j=k-1; j>=0; j--){
// comparerはこんな感じ。
const comparer = (j===k-1 ? (1<<(j+1))-1 : (1<<j));
m.push(comparer);
}
}
相方さえ見つかれば、すべて順コンパレータなので、普通に大小比較ですね。これも対称差で書いてます。対称差便利なんですよ。なので多用しています。すごく簡便です。やはり順コンパレータと逆コンパレータが混在していると分かりにくいですよね...こっちの方がすっきりしていいですね。
要素数が2べきでない場合
このやり方だとすべて昇順比較ですから、もし要素数が2べきでない場合、便宜上の「めっちゃ大きい要素」を最後に詰めて置いておいて、比較対象がそれになった場合は動かさないことにすれば、要素数が2べきでなくても普通にソートを実行できます。ただしステップ数はそれより大きい最小の2べきと同じになります。たとえば400の場合は512と同じになります。
function setup() {
createCanvas(400, 600);
const rArray = [];
const r0 = [];
for(let i=0; i<400; i++){
r0.push(random(400));
}
rArray.push(r0);
// ソートが完了したやつをぶちこんでいく
// ソートが完了したやつをぶちこんでいく
const createBitonic = (r, c) => {
const s = new Array(400);
// rをbitonicしてsにぶち込んで返す
for(let i=0; i<400; i++){
const other = i ^ c;
const selfValue = r[i];
const existValue = (other < 400);
const otherValue = (existValue ? r[other] : 0);
// 相方と大小を調べるだけなので簡便です。
if(((i<other) ^ (selfValue < otherValue)) & existValue){
s[i] = otherValue;
}else{
s[i] = selfValue;
}
}
return s;
}
const m = [];
for(let k=1; k<=9; k++){
for(let j=k-1; j>=0; j--){
// comparerはこんな感じ。
const comparer = (j===k-1 ? (1<<(j+1))-1 : (1<<j));
m.push(comparer);
}
}
for(let i=0; i<m.length; i++){
rArray.push(createBitonic(rArray[rArray.length-1], m[i]));
}
background(100,150,200);
noStroke();
colorMode(HSL,1,1,1);
const bandWidth = 600/rArray.length; // 11.13くらい
for(let i=0; i<rArray.length; i++){
const y = i*bandWidth;
for(let t=0; t<400; t++){
fill(0.3, 0.5, rArray[i][t]/400);
rect(t,y,1,bandWidth);
}
}
// check. sortに失敗していたらエラーが出る。
const result = rArray[rArray.length-1];
for(let i=0; i<399; i++){
if(result[i]>result[i+1]){ console.error("failure!"); break; }
}
}
ポイントはここです：
// 相方と大小を調べるだけなので簡便です。
if(((i<other) ^ (selfValue < otherValue)) & existValue){
s[i] = otherValue;
}else{
s[i] = selfValue;
}
すなわち相方が存在するかどうかのフラグを用意して、それがtrueなら普通に判定し、falseの場合は問答無用で据え置きにします。それを「&」で表現しています。
おわりに
2べきでなくても使えるのは便利ですね。
ここまでお読みいただいてありがとうございました。
追記：GPGPUバイトニックソートを任意個で実行する
GPU sortの方もこれで任意個に拡張できます。前回：
のコードを書き換えました。
ほぼ同じなので、コードはリンク先を参照してください。フラグメントシェーダだけ載せておきます。
#version 300 es
precision highp float;
precision highp int; // これがないとスマホなどの環境で失敗する可能性がある
in vec2 vUv;
uniform sampler2D uTex;
uniform ivec2 uTexSize; // テクスチャサイズ
uniform int uCount; // 総数
uniform int uComparer; // 比較子
out vec4 fragColor;
void main(){
// vUvから位置を作る
ivec2 selfPos = ivec2(int(floor(vUv.x*float(uTexSize.x))), int(floor(vUv.y*float(uTexSize.y))));
int self = selfPos.x + selfPos.y * uTexSize.x;
int other = self ^ uComparer;
bool otherExist = (other < uCount); // otherが存在するかどうか
ivec2 otherPos = ivec2(other % uTexSize.x, other / uTexSize.x);
vec4 selfValue = texelFetch(uTex, selfPos, 0);
// otherが存在しない場合は使わないので、ダミーを用意する。
vec4 otherValue = (otherExist ? texelFetch(uTex, otherPos, 0) : vec4(0.0));
if(((self < other) ^^ (selfValue.x < otherValue.x)) && otherExist){
fragColor = otherValue;
}else{
fragColor = selfValue;
}
}
下の方で判定しているでしょう。同じですね。otherExistでotherが400x600をはみ出すかどうか調べています。はみ出す場合は据え置きというわけです。これでしっかりソートされることを確認してみてください。