Parallel-algorithm-sorting

並列アルゴリズム-ソート

並べ替えは、特定の順序、つまり昇順、降順、アルファベット順などでグループ内の要素を配置するプロセスです。 ここでは、以下について説明します-

• 列挙ソート
• 奇偶転置ソート
• 並列マージソート
• ハイパークイックソート

要素のリストのソートは非常に一般的な操作です。 大量のデータをソートする必要がある場合、順次ソートアルゴリズムは十分に効率的ではない場合があります。 したがって、並べ替えには並列アルゴリズムが使用されます。

列挙ソート

列挙ソートは、ソートされたリスト内の各要素の最終位置を見つけることにより、リスト内のすべての要素を配置する方法です。 これは、各要素を他のすべての要素と比較し、値の小さい要素の数を見つけることによって行われます。

したがって、任意の2つの要素、a〜i〜およびa〜j〜については、次のいずれかの場合に該当する必要があります-

• a〜i〜<a〜j〜
• a〜i〜> a〜j〜
• a〜i〜= a〜j〜

アルゴリズム

procedure ENUM_SORTING (n)

begin
   for each process P1,j do
      C[j] := 0;

   for each process Pi, j do

      if (A[i] < A[j]) or A[i] = A[j] and i < j) then
         C[j] := 1;
      else
         C[j] := 0;

   for each process P1, j do
      A[C[j]] := A[j];

end ENUM_SORTING

奇偶転置ソート

奇偶転置ソートは、バブルソート手法に基づいています。 最初の番号が2番目の番号よりも大きい場合、2つの隣接する番号を比較して、昇順リストを取得します。 逆の場合は、降順のシリーズに適用されます。 奇数-偶数転置ソートは、*奇数フェーズ*と*偶数フェーズ*の2つのフェーズで動作します。 両方のフェーズで、プロセスは番号を隣接する右側の番号と交換します。

奇数-偶数転置ソート

アルゴリズム

procedure ODD-EVEN_PAR (n)

begin
   id := process's label

   for i := 1 to n do
   begin

      if i is odd and id is odd then
         compare-exchange_min(id + 1);
      else
         compare-exchange_max(id - 1);

      if i is even and id is even then
         compare-exchange_min(id + 1);
      else
         compare-exchange_max(id - 1);

   end for

end ODD-EVEN_PAR

並列マージソート

マージソートは、最初にソートされていないリストを可能な限り小さいサブリストに分割し、隣接するリストと比較して、ソートされた順序でマージします。 分割統治アルゴリズムに従って並列処理を非常にうまく実装します。

並列マージソート

アルゴリズム

procedureparallelmergesort(id, n, data, newdata)

begin
   data = sequentialmergesort(data)

      for dim = 1 to n
         data = parallelmerge(id, dim, data)
      endfor

   newdata = data
end

ハイパークイックソート

ハイパークイックソートは、ハイパーキューブでのクイックソートの実装です。 その手順は次のとおりです-

• ソートされていないリストを各ノードに分割します。
• 各ノードをローカルで並べ替えます。
• ノード0から、中央値をブロードキャストします。
• 各リストをローカルで分割し、次に最大次元で半分を交換します。
• 次元が0に達するまで、ステップ3と4を並行して繰り返します。

アルゴリズム

procedure HYPERQUICKSORT (B, n)
begin

   id := process’s label;

   for i := 1 to d do
      begin
      x := pivot;
      partition B into B1 and B2 such that B1 ≤ x < B2;
      if ith bit is 0 then

      begin
         send B2 to the process along the ith communication link;
         C := subsequence received along the ith communication link;
         B := B1 U C;
      endif

      else
         send B1 to the process along the ith communication link;
         C := subsequence received along the ith communication link;
         B := B2 U C;
         end else
      end for

   sort B using sequential quicksort;

end HYPERQUICKSORT