Algorytm równoległy - sortowanie

Sortowanie to proces porządkowania elementów w grupie w określonej kolejności, tj. W kolejności rosnącej, malejącej, alfabetycznej itp. Omówimy tutaj:

Sortowanie według wyliczenia
Sortowanie transpozycji nieparzyste-parzyste
Sortowanie równoległe ze scalaniem
Hyper Quick Sort

Sortowanie listy elementów jest bardzo powszechną operacją. Algorytm sortowania sekwencyjnego może nie być wystarczająco wydajny, gdy musimy sortować ogromną ilość danych. Dlatego do sortowania używane są algorytmy równoległe.

Sortowanie według wyliczenia

Sortowanie wyliczeniowe to metoda uporządkowania wszystkich elementów na liście poprzez znalezienie ostatecznej pozycji każdego elementu na posortowanej liście. Odbywa się to poprzez porównanie każdego elementu ze wszystkimi innymi elementami i znalezienie liczby elementów o mniejszej wartości.

Dlatego dla dowolnych dwóch elementów a _i oraz a _j musi być spełniony dowolny z poniższych przypadków -

a _i <a _j
a _i > a _j
a _i = a _j

Algorytm

procedure ENUM_SORTING (n)

begin
   for each process P_1,j do
      C[j] := 0;
		
   for each process P_{i, 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

Sortowanie transpozycji nieparzyste-parzyste

Sortowanie z transpozycją nieparzyste-parzyste jest oparte na technice sortowania bąbelkowego. Porównuje dwie sąsiednie liczby i zamienia je, jeśli pierwsza liczba jest większa niż druga, aby uzyskać listę rosnącą. Odwrotny przypadek dotyczy szeregu malejącego. Sortowanie transpozycji Odd-Even działa w dwóch fazach -odd phase i even phase. W obu fazach procesy wymieniają numery z sąsiednimi numerami po prawej stronie.

Algorytm

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

Sortowanie równoległe ze scalaniem

Sortowanie przez scalanie najpierw dzieli nieposortowaną listę na najmniejsze możliwe listy podrzędne, porównuje ją z listą sąsiednią i scala w kolejności posortowanej. Bardzo ładnie implementuje równoległość, postępując zgodnie z algorytmem dziel i zwyciężaj.

Algorytm

procedureparallelmergesort(id, n, data, newdata)

begin
   data = sequentialmergesort(data)
	
      for dim = 1 to n
         data = parallelmerge(id, dim, data)
      endfor
		
   newdata = data
end

Hyper Quick Sort

Sortowanie hiperszybkie to implementacja sortowania szybkiego na hipersześcianie. Jego kroki są następujące -

Podziel nieposortowaną listę między każdy węzeł.
Sortuj każdy węzeł lokalnie.
Z węzła 0 rozgłaszaj medianę.
Podziel każdą listę lokalnie, a następnie zamień połówki w najwyższym wymiarze.
Powtarzaj kroki 3 i 4 równolegle, aż wymiar osiągnie 0.

Algorytm

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