バイトニックソートは、マージソートの並列と言われており、並列プログラミングにおいては良く使われている(らしい)。前回の単純選択ソートは、シーケンシャルに最小値を選んで、それを順番に交換していくのだった。では、ソフトウェアの世界において並列化がし易いと言われるバイトニックソートを高位合成するとどうなるのだろう？

C言語におけるバイトニックソートの実装

バイトニックソートの本体

WikipediaでのJavaの実装を参考にした。サブルーチンが呼ばれないように、一つのルーチンにまとめている。

Bitonic sorter - Wikipedia, the free encyclopedia

#define DATA_NUM 128

void bitonic_sort (const int logn, int array[DATA_NUM]) {
  for(int p = 0;p < logn; p++) {
    for(int q = 0;q <= p; q++) {
      int d = 1 << (p-q);
      for(int i = 0; i < DATA_NUM; i++) {
        int up = ((i >> p) & 2) == 0;
        if ((i & d) == 0 && (array[i] > array[i | d]) == up) {
          int t = array[i]; array[i] = array[i | d]; array[i | d] = t;
        }
      }
    }
  }
}

テストパタンの実装

これは前回の単純選択ソートの実装とほとんど同一だ。printfでソート結果を確認してみよう。

#include <stdio.h>
#include <stdlib.h>

#define MAX_DATA 128
#define LOG_N    7

int main(void)
{
    int i;
    int x[MAX_DATA];

    for(i = 0; i < MAX_DATA; i++) {
        x[i] = rand();
    }

    printf("Before Sorting\n");
    for (i = 0; i < MAX_DATA; i++)
        printf("%d\t", x[i]);

    bitonic_sort (LOG_N, x);

    printf("After sorting\n");
    for (i = 0; i < MAX_DATA; i++)
        printf("%d\t", x[i]);

    return 0;
}