并行算法-排序

---

排序是按特定顺序排列组中元素的过程，即升序、降序、字母顺序等。这里我们将讨论以下内容 -

• 枚举排序
• 奇偶转置排序
• 并行归并排序
• 超快速排序

对元素列表进行排序是一种非常常见的操作。当我们必须对大量数据进行排序时，顺序排序算法可能不够高效。因此，排序时采用并行算法。

枚举排序

枚举排序是一种通过查找已排序列表中每个元素的最终位置来排列列表中所有元素的方法。它是通过将每个元素与所有其他元素进行比较并找到具有较小值的元素的数量来完成的。

因此，对于任意两个元素 a _i和 a _j ，以下任何一种情况都必须为真 -

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

算法

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

奇偶转置排序

奇偶转置排序基于冒泡排序技术。它比较两个相邻的数字，如果第一个数字大于第二个数字，则将它们交换，以获得升序列表。相反的情况适用于降序序列。奇偶转置排序分两个阶段进行：奇数阶段和偶数阶段。在这两个阶段中，进程都会与其右侧的相邻数字交换数字。

算法

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