อัลกอริทึมแบบขนาน - การเรียงลำดับ

การเรียงลำดับเป็นกระบวนการจัดเรียงองค์ประกอบในกลุ่มตามลำดับเฉพาะกล่าวคือเรียงลำดับจากน้อยไปหามากลำดับจากมากไปหาน้อยลำดับตัวอักษร ฯลฯ ในที่นี้จะกล่าวถึงสิ่งต่อไปนี้ -

• เรียงลำดับการแจงนับ
• การเรียงลำดับคี่ - คู่
• เรียงลำดับการผสานแบบขนาน
• จัดเรียงด่วนอย่างรวดเร็ว

การจัดเรียงรายการองค์ประกอบเป็นการดำเนินการที่พบบ่อยมาก อัลกอริทึมการเรียงลำดับตามลำดับอาจไม่มีประสิทธิภาพเพียงพอเมื่อเราต้องจัดเรียงข้อมูลจำนวนมาก ดังนั้นจึงใช้อัลกอริทึมแบบขนานในการเรียงลำดับ

เรียงลำดับการแจงนับ

การเรียงลำดับการแจงนับเป็นวิธีการจัดเรียงองค์ประกอบทั้งหมดในรายการโดยการค้นหาตำแหน่งสุดท้ายของแต่ละองค์ประกอบในรายการที่เรียงลำดับ ทำได้โดยการเปรียบเทียบแต่ละองค์ประกอบกับองค์ประกอบอื่น ๆ ทั้งหมดและค้นหาจำนวนองค์ประกอบที่มีค่าน้อยกว่า

ดังนั้นสำหรับการใด ๆ สององค์ประกอบที่_ฉันและ_เจหนึ่งในกรณีดังต่อไปนี้ต้องเป็นจริง -

• _ฉัน <a _J
• ก_i > a _j
• _ฉัน = 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

การเรียงลำดับคี่ - คู่

Odd-Even Transposition Sort ขึ้นอยู่กับเทคนิค Bubble Sort จะเปรียบเทียบตัวเลขสองตัวที่อยู่ติดกันและสลับตัวเลขหากตัวเลขแรกมากกว่าตัวเลขที่สองเพื่อให้ได้รายการลำดับจากน้อยไปมาก กรณีตรงกันข้ามใช้กับลำดับจากมากไปหาน้อย การเรียงลำดับการขนย้ายคี่ - คู่ทำงานในสองขั้นตอน -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

จัดเรียงด่วนอย่างรวดเร็ว

Hyper quick sort คือการนำการจัดเรียงอย่างรวดเร็วไปใช้บนไฮเปอร์คิวบ์ ขั้นตอนมีดังนี้ -

• แบ่งรายการที่ไม่เรียงลำดับระหว่างแต่ละโหนด
• จัดเรียงแต่ละโหนดในเครื่อง
• จากโหนด 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