C++でのバイトニックソート

---

バイトニックソートは、最適な実装のために作成された並列ソートアルゴリズムであり、ハードウェアと並列プロセッサアレイで最適に使用されます。 。

ただし、マージソートと比較すると、最も効果的なものではありません。ただし、並列実装には適しています。これは、事前定義された比較シーケンスにより、ソートされるデータから独立して比較が行われるためです。

バイトニックソートが効果的に機能するためには、要素の数が特定のタイプの数量、つまり 2 ^ nの順序である必要があります。 。

バイトニックソートの主要な部分の1つは、要素値が最初に増加するシーケンスであるバイトニックシーケンスです。 その後、減少 。

バイトニックシーケンス 0からn-1の範囲内にインデックス値iがある場合、は配列arr [0…（n-1）]です。 arr[i]の値が配列内で最大であるもの。つまり、

arr[0] <= arr[1] … <= arr[i] and arr[i] >= arr[i+1] … >= aar[n-1]

バイトニックシーケンスの特殊な特性-

• BitonicシーケンスはBitonicシーケンスに戻すことができます。

• 要素が昇順および降順であるシーケンスは、バイトニックシーケンスです。

バイトニックシーケンスの作成

ビットニックシーケンスを作成するために、2つのサブシーケンスを作成します。1つは昇順の要素を持ち、もう1つは降順の要素を持ちます。

たとえば、シーケンスarr []を見て、次のシーケンスをバイトニックシーケンスに変換してみましょう。

arr[] = {3, 4, 1, 9, 2, 7, 5, 6}

まず、要素のペアを作成し、次に、一方が昇順でもう一方が降順になるように、これらのビットニックシーケンスを作成します。

アレイでは、バイトニックシーケンスでペアを作成しましょう。

arr[] = {(3, 4), (1, 9), (2, 7), (5, 6)}
// creating bitonic sequence pairs…
arr[] = {(3, 4), (9, 1), (2, 7), (6, 5)}

次に、これらのペアのペアを作成します。つまり、4つの要素のバイトニックシーケンスと比較要素は2つの距離です[つまり、 i with i+2]。

arr[] = {(3, 4, 9, 1), (2, 7, 6, 5)}

最初のセットの昇順バイトニックは、-

として作成されます。

(3, 4, 9, 1) : comparing two distant elements.
(3, 1, 9, 4) : Now, check adjacent elements.
(1, 3, 4, 9) -> ascending bitonic sequence.

2番目のセットの降順のbitonicは、-

として作成されます。

(2, 7, 6, 5) : comparing two distant elements.
(6, 7, 2, 5) : Now, check adjacent elements.
(7, 6, 5, 2) -> descending bitonic sequence.

最後に、サイズ8のバイトニックシーケンスを取得します。

1, 3, 4, 9, 7, 6, 5, 2

さて、私たちはバイトニックシーケンスについて学んだので。 バイトニックソートについて知っておく必要があります 。

バイトニックソート

これらの手順を使用してバイトニックソートを使用してバイトニックシーケンスをソートするには-

ステップ1 −バイトニックシーケンスを作成します。

ステップ2 −これで、ある部分が昇順で、他の部分が降順であるバイトニックシーケンスができました。

ステップ3 −両方の半分の最初の要素を比較して交換します。次に、それらの2番目、3番目、4番目の要素。

ステップ4 −シーケンスの1つおきの要素を比較して交換します。

ステップ5 −最後に、シーケンスの隣接する要素を比較して交換します。

ステップ6 −すべてのスワップの後、ソートされた配列を取得します。

例

バイトニックソートの実装を示すプログラム-

#include<iostream>
using namespace std;
void bitonicSeqMerge(int a[], int start, int BseqSize, int direction) {
   if (BseqSize>1){
      int k = BseqSize/2;
      for (int i=start; i<start+k; i++)
      if (direction==(a[i]>a[i+k]))
      swap(a[i],a[i+k]);
      bitonicSeqMerge(a, start, k, direction);
      bitonicSeqMerge(a, start+k, k, direction);
   }
}
void bitonicSortrec(int a[],int start, int BseqSize, int direction) {
   if (BseqSize>1){
      int k = BseqSize/2;
      bitonicSortrec(a, start, k, 1);
      bitonicSortrec(a, start+k, k, 0);
      bitonicSeqMerge(a,start, BseqSize, direction);
   }
}
void bitonicSort(int a[], int size, int up) {
   bitonicSortrec(a, 0, size, up);
}
int main() {
   int a[]= {5, 10, 51, 8, 1, 9, 6, 22};
   int size = sizeof(a)/sizeof(a[0]);
   printf("Original array: \n");
   for (int i=0; i<size; i++)
   printf("%d\t", a[i]);
   bitonicSort(a, size, 1);
   printf("\nSorted array: \n");
   for (int i=0; i<size; i++)
   printf("%d\t", a[i]);
   return 0;
}

出力

Original array:
5 10 51 8 1 9 6 22
Sorted array:
1 5 6 8 9 10 22 51