Параллельный алгоритм - сортировка

Сортировка - это процесс расположения элементов в группе в определенном порядке, то есть в порядке возрастания, убывания, алфавитного порядка и т. Д. Здесь мы обсудим следующее:

Сортировка перечислением
Сортировка нечетно-четным транспонированием
Параллельная сортировка слиянием
Сверхбыстрая сортировка

Сортировка списка элементов - очень распространенная операция. Алгоритм последовательной сортировки может быть недостаточно эффективным, когда нам нужно отсортировать огромный объем данных. Поэтому при сортировке используются параллельные алгоритмы.

Сортировка перечислением

Сортировка перечислением - это метод упорядочивания всех элементов в списке путем поиска конечной позиции каждого элемента в отсортированном списке. Это делается путем сравнения каждого элемента со всеми другими элементами и определения количества элементов, имеющих меньшее значение.

Следовательно, для любых двух элементов a _i и a _j должен выполняться любой из следующих случаев:

_я <а _J
а _я > а _j
а _я = а _j

Алгоритм

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

Сортировка нечетно-четным транспонированием

Сортировка с транспонированием нечетного и четного основана на методе пузырьковой сортировки. Он сравнивает два соседних числа и переключает их, если первое число больше второго, чтобы получить список в порядке возрастания. Противоположный случай применяется для серии по убыванию. Сортировка нечетной-четной перестановки работает в два этапа:odd phase и even phase. На обеих фазах процессы обмениваются номерами с соседними номерами справа.

Алгоритм

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

Параллельная сортировка слиянием

Сортировка слиянием сначала делит несортированный список на минимально возможные подсписки, сравнивает его с соседним списком и объединяет его в отсортированном порядке. Он очень хорошо реализует параллелизм, следуя алгоритму разделяй и властвуй.

Алгоритм

procedureparallelmergesort(id, n, data, newdata)

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

Сверхбыстрая сортировка

Гипербыстрая сортировка - это реализация быстрой сортировки на гиперкубе. Его шаги следующие -

Разделите несортированный список между каждым узлом.
Отсортируйте каждый узел локально.
Из узла 0 транслируйте медианное значение.
Разделите каждый список локально, а затем обменяйте половинки по самому высокому измерению.
Повторите шаги 3 и 4 параллельно, пока размер не достигнет 0.

Алгоритм

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