Thuật toán song song - Sắp xếp

Sắp xếp là một quá trình sắp xếp các phần tử trong một nhóm theo một thứ tự cụ thể, tức là thứ tự tăng dần, thứ tự giảm dần, thứ tự bảng chữ cái, v.v. Ở đây chúng ta sẽ thảo luận về những điều sau:

Sắp xếp liệt kê
Sắp xếp chuyển vị chẵn lẻ
Sắp xếp hợp nhất song song
Sắp xếp siêu nhanh

Sắp xếp danh sách các phần tử là một hoạt động rất phổ biến. Thuật toán sắp xếp tuần tự có thể không đủ hiệu quả khi chúng ta phải sắp xếp một khối lượng lớn dữ liệu. Do đó, các thuật toán song song được sử dụng trong việc sắp xếp.

Sắp xếp liệt kê

Sắp xếp kiểu liệt kê là một phương pháp sắp xếp tất cả các phần tử trong một danh sách bằng cách tìm vị trí cuối cùng của mỗi phần tử trong một danh sách đã sắp xếp. Nó được thực hiện bằng cách so sánh mỗi phần tử với tất cả các phần tử khác và tìm số phần tử có giá trị nhỏ hơn.

Do đó, với bất kỳ hai phần tử nào, a _i và a _j bất kỳ một trong các trường hợp sau phải đúng:

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

Thuật toán

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

Sắp xếp chuyển vị chẵn lẻ

Sắp xếp chuyển vị chẵn lẻ dựa trên kỹ thuật Sắp xếp bong bóng. Nó so sánh hai số liền kề và chuyển đổi chúng, nếu số đầu tiên lớn hơn số thứ hai để có được danh sách thứ tự tăng dần. Trường hợp ngược lại áp dụng cho chuỗi thứ tự giảm dần. Sắp xếp chuyển vị Lẻ-Chẵn hoạt động theo hai giai đoạn:odd phase và even phase. Trong cả hai giai đoạn, các quá trình trao đổi số với số liền kề của chúng ở bên phải.

Thuật toán

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

Sắp xếp hợp nhất song song

Sắp xếp hợp nhất trước tiên chia danh sách chưa được sắp xếp thành các danh sách con nhỏ nhất có thể, so sánh nó với danh sách liền kề và hợp nhất nó theo thứ tự đã sắp xếp. Nó thực hiện song song rất độc đáo bằng cách tuân theo thuật toán chia và chinh phục.

Thuật toán

procedureparallelmergesort(id, n, data, newdata)

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

Sắp xếp siêu nhanh

Sắp xếp siêu nhanh là một triển khai sắp xếp nhanh trên siêu khối. Các bước của nó như sau:

Chia danh sách chưa được sắp xếp cho mỗi nút.
Sắp xếp cục bộ từng nút.
Từ nút 0, phát giá trị trung bình.
Tách cục bộ từng danh sách, sau đó trao đổi các nửa theo thứ nguyên cao nhất.
Lặp lại bước 3 và bước 4 song song cho đến khi thứ nguyên về 0.

Thuật toán

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