Paralel Algoritma - Sıralama

Sıralama, bir gruptaki öğeleri belirli bir sırayla düzenleme işlemidir, yani artan sıra, azalan sıra, alfabetik sıra vb. Burada aşağıdakileri tartışacağız -

Numaralandırma Sıralaması
Tek-Çift Aktarım Sıralaması
Paralel Birleştirme Sıralaması
Hiper Hızlı Sıralama

Bir öğe listesinin sıralanması çok yaygın bir işlemdir. Sıralı bir sıralama algoritması, büyük hacimli verileri sıralamak zorunda olduğumuzda yeterince verimli olmayabilir. Bu nedenle, sıralamada paralel algoritmalar kullanılır.

Numaralandırma Sıralaması

Numaralandırma sıralaması, sıralı bir listedeki her bir öğenin son konumunu bularak bir listedeki tüm öğeleri düzenleme yöntemidir. Her bir öğeyi diğer tüm öğelerle karşılaştırarak ve daha küçük değere sahip öğe sayısını bularak yapılır.

Bu nedenle, herhangi iki öğe için a _i ve a _j aşağıdaki durumlardan herhangi biri doğru olmalıdır -

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

Algoritma

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

Tek-Çift Aktarım Sıralaması

Tek-Çift Transpozisyon Sıralama, Kabarcık Sıralama tekniğine dayanır. İlk sayı ikinci sayıdan büyükse, artan sıra listesi almak için iki bitişik sayıyı karşılaştırır ve değiştirir. Tersi durum bir azalan sıra dizisi için geçerlidir. Tek-Çift aktarım sıralaması iki aşamada çalışır -odd phase ve even phase. Her iki aşamada da işlemler, sağdaki bitişik sayıları ile sayı alışverişinde bulunur.

Algoritma

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

Paralel Birleştirme Sıralaması

Birleştirme sıralaması ilk olarak sıralanmamış listeyi mümkün olan en küçük alt listelere böler, onu bitişik listeyle karşılaştırır ve sıralı bir sırada birleştirir. Böl ve fethet algoritmasını takip ederek paralelliği çok güzel bir şekilde uygular.

Algoritma

procedureparallelmergesort(id, n, data, newdata)

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

Hiper Hızlı Sıralama

Hiper hızlı sıralama, hiperküp üzerinde hızlı sıralamanın bir uygulamasıdır. Adımları aşağıdaki gibidir -

Sıralanmamış listeyi her düğüm arasında bölün.
Her düğümü yerel olarak sıralayın.
0 düğümünden medyan değeri yayınlayın.
Her listeyi yerel olarak bölün, ardından yarıları en yüksek boyutta değiştirin.
Boyut 0'a ulaşana kadar 3. ve 4. adımları paralel olarak tekrarlayın.

Algoritma

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