Algorithme parallèle - Tri

Le tri est un processus qui consiste à organiser les éléments d'un groupe dans un ordre particulier, c'est-à-dire dans l'ordre croissant, dans l'ordre décroissant, dans l'ordre alphabétique, etc. Nous aborderons ici ce qui suit -

Tri d'énumération
Tri de transposition pair-impair
Tri de fusion parallèle
Tri hyper rapide

Le tri d'une liste d'éléments est une opération très courante. Un algorithme de tri séquentiel peut ne pas être assez efficace lorsque nous devons trier un énorme volume de données. Par conséquent, des algorithmes parallèles sont utilisés pour le tri.

Tri d'énumération

Le tri par énumération est une méthode d'organisation de tous les éléments dans une liste en recherchant la position finale de chaque élément dans une liste triée. Cela se fait en comparant chaque élément avec tous les autres éléments et en trouvant le nombre d'éléments ayant une valeur inférieure.

Par conséquent, pour deux éléments quelconques, a _i et a _j l'un quelconque des cas suivants doit être vrai -

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

Algorithme

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

Tri de transposition pair-impair

Le tri par transposition impair-pair est basé sur la technique du tri à bulles. Il compare deux nombres adjacents et les change, si le premier nombre est supérieur au deuxième nombre pour obtenir une liste d'ordre croissant. Le cas contraire s'applique pour une série par ordre décroissant. Le tri de transposition impair-pair fonctionne en deux phases -odd phase et even phase. Dans les deux phases, les processus échangent des numéros avec leur numéro adjacent à droite.

Algorithme

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

Tri de fusion parallèle

Le tri par fusion divise d'abord la liste non triée en sous-listes les plus petites possibles, la compare à la liste adjacente et la fusionne dans un ordre trié. Il implémente très bien le parallélisme en suivant l'algorithme de division et de conquête.

Algorithme

procedureparallelmergesort(id, n, data, newdata)

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

Tri hyper rapide

Le tri hyper rapide est une implémentation du tri rapide sur hypercube. Ses étapes sont les suivantes -

Divisez la liste non triée entre chaque nœud.
Triez chaque nœud localement.
À partir du nœud 0, diffusez la valeur médiane.
Divisez chaque liste localement, puis échangez les moitiés dans la dimension la plus élevée.
Répétez les étapes 3 et 4 en parallèle jusqu'à ce que la cote atteigne 0.

Algorithme

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