Block_swap_algorithms
ブロックスワップアルゴリズムは、コンピュータアルゴリズムの配列の2つの要素をスワップします。同じサイズの配列の重複しない2つの領域を交換するのは簡単です。ただし、配列の重複しない2つの領域をインプレースで交換することは簡単ではありません。これらの領域は、互いに隣接していますが、サイズが異なります。これを実現するための3つのアルゴリズムが知られています：Bentley’s Juggling、Gries-Mills、およびReversal。 3つのアルゴリズムはすべて線形時間O（n）です（時間計算量を参照）。
反転アルゴリズム
反転アルゴリズムは、回転を使用して説明するのが最も簡単です。回転は、配列要素のインプレース反転です。このメソッドは、配列の2つの要素を範囲内の外部から交換します。回転は、偶数の要素または奇数の配列要素に対して機能します。反転アルゴリズムは、3つのインプレースローテーションを使用して、インプレースブロックスワップを実行します。
領域Aを回転します
領域Bを回転します
領域ABを回転させる
Gries-MillsおよびReversalアルゴリズムは、キャッシュに適したメモリアクセスパターンの動作により、BentleyのJugglingよりも優れたパフォーマンスを発揮します。
回転はサブ領域に分割でき、他の領域とは独立して回転できるため、反転アルゴリズムは適切に並列化されます。
参考文献
^ Jon Bentley、「Programming Pearls」、pp。13–15、209-211。
同様の記事でリストできるように、カテゴリを追加して