奇数偶数タイプ

コンピューティングにおいて、奇偶ソートまたは奇偶転置ソート（ブリックソート^{[ 1 ]}またはパリティソートとも呼ばれる）は、比較的単純なソートアルゴリズムであり、元々はローカル相互接続を備えた並列プロセッサで使用するために開発されました。これはバブルソートに関連する比較ソートであり、多くの特徴を共有しています。このアルゴリズムは、リスト内の隣接する要素のすべての奇数/偶数インデックスのペアを比較し、順序が間違っているペア（最初の要素が2番目の要素より大きい場合）を交換することによって機能します。次のステップでは、偶数/奇数インデックスのペア（隣接する要素）に対してこれを繰り返します。その後、リストがソートされるまで、奇数/偶数ステップと偶数/奇数ステップを交互に繰り返します。

並列プロセッサでは、プロセッサごとに 1 つの値があり、ローカルな左右の隣接接続のみがある場合、プロセッサはすべて同時に隣接プロセッサとの比較交換操作を実行し、奇数-偶数と偶数-奇数のペアを交互に行います。このアルゴリズムは、1972 年にHabermannによって最初に発表され、このようなプロセッサで効率的であることが示されました。 ^{[ 2 ]}

このアルゴリズムは、プロセッサごとに複数の項目がある場合にも効率的に拡張できます。Baudet–Stevensonの奇偶マージ分割アルゴリズムでは、各プロセッサは各ステップで任意の効率的なソートアルゴリズムを使用して自身のサブリストをソートし、その後、隣接するプロセッサとのマージ分割、または転置マージ操作を実行します。このとき、各ステップで隣接ペアリングは奇偶と偶奇の間で交互に行われます。^{[ 3 ]}

関連するが、より効率的なソートアルゴリズムとして、比較交換操作と完全シャッフル操作を使用するBatcherの奇偶マージソートがある。 ^{[ 4 ]} Batcherの方法は、長距離接続を備えた並列プロセッサで効率的である。^{[ 5 ]}

バブルソートのようなシングルプロセッサアルゴリズムは単純だが、効率はあまり良くない。ここでは、0から始まるインデックスを前提とする。

function oddEvenSort ( list ) { function swap ( list , i , j ) { var temp = list [ i ]; list [ i ] = list [ j ]; list [ j ] = temp ; }var sorted = false ; while ( ! sorted ) { sorted = true ; for ( var i = 1 ; i < list.length - 1 ; i += 2 ) { if ( list [ i ] > list [ i + 1 ] ) { swap ( list , i , i + 1 ); sorted = false ; } } for ( var i = 0 ; i < list.length - 1 ; i + = 2 ) { if ( list [ i ] > list [ i + 1 ] ) { swap ( list , i , i + 1 ) ; sorted = false ; } } } }

主張:${\displaystyle a_{1},...,a_{n}}$< で順序付けられたデータのシーケンスである。奇数偶数ソートアルゴリズムは、このデータを正しくソートする。${\displaystyle n}$パス。（ここでいうパスとは、奇数と偶数、または偶数と奇数の比較の完全なシーケンスを指します。パスは、パス1：奇数と偶数、パス2：偶数と奇数、といった順序で発生します。）

証拠：

この証明はトーマス・ウォルシュによる証明に大まかに基づいている。^{[ 6 ]}

ソートアルゴリズムは比較交換操作のみを含み、データに依存しない（比較交換操作の順序はデータに依存しない）ため、クヌースの0-1ソート原理^{[ 7 ] [ 8 ]}によれば、各${\displaystyle a_{i}}$は0または1のいずれかです。${\displaystyle e}$1秒。

右端の 1 は偶数または奇数の位置にある可能性があるため、最初の奇数-偶数パスでは移動しない可能性があります。しかし、最初の奇数-偶数パスの後、右端の 1 は偶数の位置になります。したがって、残りのすべてのパスで右に移動します。右端の 1 は、${\displaystyle e}$最大で移動する必要があります${\displaystyle ne}$手順。したがって、最大で${\displaystyle n-e+1}$パスを実行して、一番右の1を正しい位置に移動させます。

次に、右から2番目の1を考えてみましょう。2回のパスの後、その右にある1は少なくとも1ステップ右に移動します。したがって、残りのすべてのパスでは、右から2番目の1を最も右の1と見なすことができます。右から2番目の1は少なくとも位置から始まります。${\displaystyle e-1}$そして最大で位置に移動する必要があります${\displaystyle n-1}$なので、最大で移動する必要があります${\displaystyle (n-1)-(e-1)=ne}$ステップ。最大 2 回通過すると、最も右の 1 はすでに移動しているので、2 番目に右の 1 の右側のエントリは 0 になります。したがって、最初の 2 回以降のすべての通過で、2 番目に右の 1 は右に移動します。したがって、最大で${\displaystyle n-e+2}$パスを実行して、右から2番目の1を正しい位置に移動させます。

この方法を続けると、帰納法によって次のことが示される。${\displaystyle i}$右端の 1 は最大で正しい位置に移動します。${\displaystyle n-e+i}$合格。${\displaystyle i\leq e}$したがって、${\displaystyle i}$右端の 1 は最大で正しい位置に移動します。${\displaystyle n-e+e=n}$通過します。したがって、リストは正しくソートされています。${\displaystyle n}$合格。証明終了。

各パスにかかる時間について言及します${\displaystyle O(n)}$ステップがあるので、このアルゴリズムには${\displaystyle O(n^{2})}$複雑。