Parallel-algorithm-sorting
提供:Dev Guides
並列アルゴリズム-ソート
並べ替えは、特定の順序、つまり昇順、降順、アルファベット順などでグループ内の要素を配置するプロセスです。 ここでは、以下について説明します-
- 列挙ソート
- 奇偶転置ソート
- 並列マージソート
- ハイパークイックソート
要素のリストのソートは非常に一般的な操作です。 大量のデータをソートする必要がある場合、順次ソートアルゴリズムは十分に効率的ではない場合があります。 したがって、並べ替えには並列アルゴリズムが使用されます。
列挙ソート
列挙ソートは、ソートされたリスト内の各要素の最終位置を見つけることにより、リスト内のすべての要素を配置する方法です。 これは、各要素を他のすべての要素と比較し、値の小さい要素の数を見つけることによって行われます。
したがって、任意の2つの要素、a〜i〜およびa〜j〜については、次のいずれかの場合に該当する必要があります-
- a〜i〜<a〜j〜
- a〜i〜> a〜j〜
- a〜i〜= a〜j〜
アルゴリズム
奇偶転置ソート
奇偶転置ソートは、バブルソート手法に基づいています。 最初の番号が2番目の番号よりも大きい場合、2つの隣接する番号を比較して、昇順リストを取得します。 逆の場合は、降順のシリーズに適用されます。 奇数-偶数転置ソートは、*奇数フェーズ*と*偶数フェーズ*の2つのフェーズで動作します。 両方のフェーズで、プロセスは番号を隣接する右側の番号と交換します。
アルゴリズム
並列マージソート
マージソートは、最初にソートされていないリストを可能な限り小さいサブリストに分割し、隣接するリストと比較して、ソートされた順序でマージします。 分割統治アルゴリズムに従って並列処理を非常にうまく実装します。
アルゴリズム
ハイパークイックソート
ハイパークイックソートは、ハイパーキューブでのクイックソートの実装です。 その手順は次のとおりです-
- ソートされていないリストを各ノードに分割します。
- 各ノードをローカルで並べ替えます。
- ノード0から、中央値をブロードキャストします。
- 各リストをローカルで分割し、次に最大次元で半分を交換します。
- 次元が0に達するまで、ステップ3と4を並行して繰り返します。