병렬 알고리즘-정렬

정렬은 특정 순서 (예 : 오름차순, 내림차순, 알파벳 순서 등)로 그룹의 요소를 배열하는 프로세스입니다. 여기서는 다음 사항에 대해 설명합니다.

열거 형 정렬
홀수 짝수 조옮김 정렬
병렬 병합 정렬
하이퍼 퀵 정렬

요소 목록을 정렬하는 것은 매우 일반적인 작업입니다. 순차 정렬 알고리즘은 대량의 데이터를 정렬해야 할 때 충분히 효율적이지 않을 수 있습니다. 따라서 정렬에는 병렬 알고리즘이 사용됩니다.

열거 형 정렬

열거 형 정렬은 정렬 된 목록에서 각 요소의 최종 위치를 찾아 목록의 모든 요소를 정렬하는 방법입니다. 각 요소를 다른 모든 요소와 비교하고 값이 작은 요소의 수를 찾아서 수행됩니다.

따라서 두 요소, a _i 및 a _j 에 대해 다음 경우 중 하나가 참이어야합니다.

a _나는 <a _j
a _i > a _j
a _i = a _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에서 중앙값을 브로드 캐스트합니다.
각 목록을 로컬로 분할 한 다음 가장 높은 차원에서 절반을 교환합니다.
치수가 0이 될 때까지 3 단계와 4 단계를 병렬로 반복합니다.

연산

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