Algoritmo paralelo: clasificación

La clasificación es un proceso de organizar elementos en un grupo en un orden particular, es decir, orden ascendente, orden descendente, orden alfabético, etc. Aquí discutiremos lo siguiente:

  • Orden de enumeración
  • Orden de transposición pares-impares
  • Orden de fusión en paralelo
  • Clasificación hiperrápida

Ordenar una lista de elementos es una operación muy común. Un algoritmo de clasificación secuencial puede no ser lo suficientemente eficiente cuando tenemos que clasificar un gran volumen de datos. Por lo tanto, se utilizan algoritmos paralelos en la clasificación.

Orden de enumeración

La ordenación por enumeración es un método para organizar todos los elementos de una lista al encontrar la posición final de cada elemento en una lista ordenada. Se hace comparando cada elemento con todos los demás elementos y encontrando el número de elementos que tienen un valor menor.

Por lo tanto, para dos elementos cualesquiera, a i y a j cualquiera de los siguientes casos debe ser verdadero:

  • a i <a j
  • a i > a j
  • a yo = 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

Orden de transposición pares-impares

La clasificación por transposición de pares pares e impares se basa en la técnica de clasificación de burbujas. Compara dos números adyacentes y los cambia, si el primer número es mayor que el segundo número para obtener una lista en orden ascendente. El caso contrario se aplica a una serie de orden descendente. La ordenación por transposición pares-impares opera en dos fases:odd phase y even phase. En ambas fases, los procesos intercambian números con su número adyacente a la derecha.

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

Orden de fusión en paralelo

Merge sort primero divide la lista sin clasificar en sublistas más pequeñas posibles, la compara con la lista adyacente y la fusiona en un orden ordenado. Implementa el paralelismo muy bien siguiendo el algoritmo de divide y vencerás.

Algoritmo

procedureparallelmergesort(id, n, data, newdata)

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

Clasificación hiperrápida

La ordenación hiperrápida es una implementación de la ordenación rápida en hipercubo. Sus pasos son los siguientes:

  • Divida la lista sin clasificar entre cada nodo.
  • Ordene cada nodo localmente.
  • Desde el nodo 0, difunda el valor mediano.
  • Divida cada lista localmente, luego intercambie las mitades en la dimensión más alta.
  • Repita los pasos 3 y 4 en paralelo hasta que la dimensión llegue a 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