sorting - 分散システムでの挿入ソート

Question

挿入ソートは、分散システムで配列の複数のコピーをどのように処理しますか？データを書くよりも読む方が簡単なのでお願いします。更新回数の観点から、分散システムのアルゴリズムのコストはどのくらいになりますか？

Answer 1

それは完全に分散挿入ソートのバージョンに依存します。1つの解決策は次のとおりです。

1. 配列A（n個の要素を持つ）は、システム内のすべてのノードで共有されます。
2. アレイAは、サブアレイA1、A2、A3、...、Apに分割できます。ここで、pはシステム内のマシンの数です。このパーティショニングは分散して実行されます。つまり、各ノードはそのサブ配列の下限と上限を見つけます。（これは、中央値を見つけて配列を分割し、中央値をもう一度見つけるなどによって行うことができます。）
3. これで、各ノードは挿入ソートを使用してスライスをソートできます。
4. 各ノードでソートされたサブ配列は、マージソートの挿入ソートのいずれかを介してマージできます。

注：更新された場合に数を数えることによって分散アルゴリズムの有効性を測定することは正しくありません。多くの更新が同時に実行される限り、実行の合計時間の複雑さを考慮に入れる必要があります。