Algoritmo Paralelo - Classificação

A classificação é um processo de organizar os elementos em um grupo em uma ordem particular, ou seja, ordem crescente, ordem decrescente, ordem alfabética, etc. Aqui, discutiremos o seguinte -

  • Classificação de enumeração
  • Classificação de transposição ímpar-par
  • Classificação de fusão paralela
  • Classificação Hiper Rápida

Classificar uma lista de elementos é uma operação muito comum. Um algoritmo de classificação sequencial pode não ser eficiente o suficiente quando temos que classificar um grande volume de dados. Portanto, algoritmos paralelos são usados ​​na classificação.

Classificação de enumeração

A classificação por enumeração é um método de organizar todos os elementos em uma lista, encontrando a posição final de cada elemento em uma lista classificada. Isso é feito comparando cada elemento com todos os outros elementos e encontrando o número de elementos com valor menor.

Portanto, para quaisquer dois elementos, a i e a j, qualquer um dos seguintes casos deve ser verdadeiro -

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

Algoritmo

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

Classificação de transposição ímpar-par

A classificação por transposição ímpar-par é baseada na técnica de classificação por bolha. Ele compara dois números adjacentes e os troca, se o primeiro número for maior que o segundo, para obter uma lista de ordem crescente. O caso oposto se aplica a uma série de ordem decrescente. A classificação de transposição ímpar-par opera em duas fases -odd phase e even phase. Em ambas as fases, os processos trocam números com seus números adjacentes à direita.

Algoritmo

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

Classificação de fusão paralela

A classificação por mesclagem divide primeiro a lista não classificada nas menores sub-listas possíveis, compara-a com a lista adjacente e a mescla em uma ordem de classificação. Ele implementa o paralelismo muito bem, seguindo o algoritmo de divisão e conquista.

Algoritmo

procedureparallelmergesort(id, n, data, newdata)

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

Classificação Hiper Rápida

A classificação hiper rápida é uma implementação de classificação rápida no hipercubo. Suas etapas são as seguintes -

  • Divida a lista não classificada entre cada nó.
  • Classifique cada nó localmente.
  • Do nó 0, transmita o valor mediano.
  • Divida cada lista localmente e, em seguida, troque as metades na dimensão mais alta.
  • Repita as etapas 3 e 4 em paralelo até que a dimensão alcance 0.

Algoritmo

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