Clever Geek Handbook

ブッチャーの偶奇結合ソート

はじめに



奇数偶数マージソートアルゴリズムは、1968年にバッチャーによって開発されました。 このアルゴリズムはあまり人気がなく、あまり有名でもありません。 ただし、並列化はかなり簡単であり、その実装はそれほど複雑ではありません。 個人的には、MPIを理解し、コースラでテストタスクを見たときに彼について知りました：肉屋の種類を書きます。



基本操作



上記のコードはパフォーマンスの点では理想的ではありませんが、アルゴリズムを理解し理解するのが最も簡単です。



アルゴリズムでは、次の3つの抽象操作が必要です。



compare-exchange-順序が狂っている要素を交換します。 



template <class T> void compexch(T& a, T&b) { if (b < a) std::swap(a, b); }


完全シャッフル -配列を半分に分割し、その結果、前半の最初の要素が結果として最初になり、後半の最初の要素が結果として2番目になり、前半の後半が結果として3番目になります。 配列は必然的に偶数の長さです。 実際、前半の要素を偶数位置に配置し、後半の要素を奇数位置に配置します。 



 template <class T> void shuffle(std::vector<T>& a, unsigned int l, unsigned int r) { auto half = (unsigned int) (l + r) / 2; std::vector<T> tmp(a.size()); unsigned int i, j; for (i = l, j = 0; i <= r; i += 2, j++) { tmp[i] = a[l + j]; tmp[i + 1] = a[half + j + 1]; } for (auto i = 0; i < tmp.size(); i++) a[i] = tmp[i]; }


完全なシャッフル解除 -前の操作と反対の操作。 偶数の位置を取る要素は結果配列の前半に送信され、奇数の要素は後半に送信されます。 



 template <class T> void unshuffle(std::vector<T>& a, unsigned int l, unsigned int r) { auto half = (unsigned int) (l + r) / 2; std::vector<T> tmp(a.size()); unsigned int i, j; for (i = l, j =0; i<=r; i += 2, j++) { tmp[l + j] = a[i]; tmp[half + j + 1] = a[i + 1]; } for (auto i = 0; i < tmp.size(); i++) a[i] = tmp[i]; }


アルゴリズム自体



ソートに関する投稿/記事/本でよくあるように、入力に来る配列のサイズは2の累乗に等しいと仮定します。 これにより、アルゴリズムの説明とその正当性の証明が簡単になります。 この制限は後で削除されます。



導入された操作を使用して、アルゴリズムは非常に簡単に定式化されます。 シャッフル解除操作を使用して、配列を2つに分割します。 次に、これらの各半分をソートしてから、シャッフル操作を使用してマージして戻す必要があります。 このアルゴリズムは、偶奇マージソートと呼ばれるだけではありません-アプローチはよく知られているマージソートに似ていますが 、半分に分割するのではなく、インデックスのパリティによって、部分に分割するロジックが異なる点が異なります。



入力された操作を使用した最も簡単な実装： 



 template <class T> void OddEvenMergeSort(std::vector<T>& a, unsigned int l, unsigned int r) { if (r == l + 1) compexch(a[l], a[r]); //     2 -     if (r < l + 2) return; //    1 - ,     unshuffle(a, l, r); //     auto half = (unsigned int) (l + r) / 2; OddEvenMergeSort(a, l, half); OddEvenMergeSort(a, half + 1, r); //    shuffle(a, l, r); //  for (auto i = l + 1; i < r; i += 2) compexch(a[i], a[i + 1]); auto halfSize = (r - l + 1) / 2 - 1; //* for (int i = l + 1; i + halfSize < r; i++) //* compexch(a[i], a[i + halfSize]); //* }


発言
私のように、「C ++の基本アルゴリズム」でSedgwickからこのアルゴリズムについて読んだ場合、OddEvenMergeSort関数に「*」とマークされた行がないことに気付くかもしれません。 すでにタイプミスか何か、私は知りません。 しかし、彼の本で与えられているアルゴリズムは、たとえば「ABABABAB」という行で間違っています。



最初のシャッフル解除呼び出しの後、「AAAABBBB」を取得します。 次に、「AAAA」と「BBBB」の部分を再帰的に呼び出します。 アルゴリズムが正しく機能すると仮定します。 次に、呼び出しの後、「AAAA」と「BBBB」の部分を取得します。 シャッフルを行い、「ABABABAB」を取得します。 ペアワイズ比較は、compexchへの4倍の呼び出し（「A」、「B」）に縮退し、何も変更されません。



3行追加すると、この問題が解決します。 将来、時間があれば、その理由を説明します。



説明



操作の原則自体は、実際にはマージソートと変わりませんが、マージ操作はまったく異なる方法で実行されます。 マージソートで2つのインデックスを取得する場合-半分が既にソートされている配列の前半と後半で、各ステップで結果として各半分に現在の最小値を入れるだけで、ここでシャッフル操作を行い、結果のペアワイズを比較します配列。



開始方法



電話するだけ 
  OddEvenMergeSort(a, 0, a.size() - 1);




2のべき乗ではない長さの配列についてはどうですか？



最も簡単な方法は、必要な数の要素を2の累乗に追加することです。これは、元の配列内の任意の要素のアプリオリよりも多い（または少ない）です。



2番目のアプローチはこれです。



なぜなら 任意の数を2の累乗の合計として表すことができます。次に、配列をそのようなサブ配列に分割し、Butcherソートで個別にソートし、 マージソートでのマージと同様の操作を使用して結合します。

同時に、小さなサブアレイは別のアルゴリズムでソートできます。たとえば、再帰呼び出しを必要としません。



作業例 



 AGINORSTAEELMPXY AIOSAEMXGNRTELPY AOAMISEX AAOM AA MO AMAO AAMO IESX EI SX ESIX EISX AEAIMSOX AAEIMOSX GREPNTLY GERP EG PR EPGR EGPR NLTY LN TY LTNY LNTY ELGNPTRY EGLNPRTY AEAGELINMPORSTXY AAEEGILMNOPRSTXY


More articles:


All Articles