読者です 読者をやめる 読者になる 読者になる

バイトニックソート書いた

バイトニックソート(bitonic sorter)は、並列処理に適した「ソーティングネットワーク」という種類のソートアルゴリズムで、直列での時間計算量はO(n log^2 n)ですが、最大nで並列できて、その結果O(log^2 n)で計算できるようになります。
マージソートの類ですが、ソート途中の流れを可視化するとギザギザな感じになってとても面白いことが特徴です。
実際のアルゴリズムは他に任せて、ここではソースだけ掲載します。

#include <cstdio>
#include <cstdlib>
#include <utility>
using namespace std;

void bitonicsort(int lgn, int *ary) {
    for(int fb=1; fb<=lgn; fb++) {
        for(int sb=fb-1; sb>=0; sb--) {
            // this loop can be parallelized
            for(int i = 0; i < (1<<lgn); i++) {
                if((i>>fb)&1^(i>>sb)&1 && ary[i] < ary[i^(1<<sb)]) {
                    swap(ary[i], ary[i^(1<<sb)]);
                }
            }
        }
    }
}

int main(int argc, char **argv)
{
    srand(10000);
    int lgn = 10;
    int *ary = new int[1<<lgn];
    for(int i = 0; i < (1<<lgn); i++) {
        ary[i] = rand()%10000;
    }
    bitonicsort(lgn, ary);
    for(int i = 0; i < (1<<lgn); i++) {
        printf("%d, ", ary[i]);
    }
    printf("\n");
    return 0;
}