奇偶転置（ブリックソート）のためのC / C ++プログラム？

奇偶転置ソートとも呼ばれる奇偶転置ソートは、バブルソートと同様のソート手法です。この並べ替え手法は、奇数フェーズと偶数フェーズの2つのフェーズに細分されます。これらのフェーズはすべて、すべての要素が並べ替えられるまで、反復ごとに同時に行われます。

奇数フェーズ このプログラミング手法の一部はバブルソートとして機能しますが、インデックスが奇数の要素に対してのみ機能します。

同様に、偶数フェーズ インデックスが偶数の要素でのみ機能します。

この概念をより明確にするために、例を見てみましょう：

Input: a[]={3,5,7,6,1,4,2}
Output: 1 2 3 4 5 6 7

説明

奇偶転置ソートは、ブリックソートとも呼ばれ、並列処理を念頭に置いて設計された単純なソート手法です。比較を使用して要素を並べ替えます。比較は、年齢と要素を含むすべての奇数/偶数ペアで行われます。いずれかのペアの順序が間違っている場合は、順序が切り替えられて正しくなります。このプロセスは、リストがソートされるまで続きます。並列プロセス用に開発されたため、プロセッサごとに1つの値を使用でき、両方のプロセスが交換比較タイプの操作で同時に動作します。このアルゴリズムは元々提示されており、そのようなプロセッサで効率的であることが示されています

例

#include <stdio.h>
#include <math.h>
#define MAX 7
void swap(int *,int *);
void oddeven_sort(int *);
int main() {
   int a[]={3,5,7,6,1,4,2}, i;
   oddeven_sort(a);
   for (i = 0;i < MAX;i++) {
      printf(" %d", a[i]);
   }
}
void swap(int * x, int * y) {
   int temp;
   temp = *x;
   *x = *y;
   *y = temp;
}
void oddeven_sort(int * x) {
   int sort = 0, i;
   while (!sort) {
      sort = 1;
      for (i = 1;i < MAX;i += 2) {
         if (x[i] > x[i+1]) {
            swap(&x[i], &x[i+1]);
            sort = 0;
         }
      }
      for (i = 0;i < MAX - 1;i += 2) {
         if (x[i] > x[i + 1]) {
            swap(&x[i], &x[i + 1]);
            sort = 0;
         }
      }
   }
}

出力

1234567