เครือข่ายการเรียงลำดับแบบคู่

การแสดงภาพเครือข่ายการเรียงลำดับแบบจับคู่ที่มีอินพุต 16 ตัว
ระดับ	อัลกอริทึมการเรียงลำดับ
โครงสร้างข้อมูล	อาร์เรย์
ประสิทธิภาพในกรณีที่เลวร้ายที่สุด	${\displaystyle (\log n)(\log n+1)/2}$เวลาคู่ขนาน
ความซับซ้อนของพื้นที่ในกรณีที่เลวร้ายที่สุด	${\displaystyle n(\log n)(\log n-1)/4+n-1}$พื้นที่และเวลาตามลำดับ
เหมาะสมที่สุด	เลขที่

เครือข่ายการเรียงลำดับแบบคู่ (pairwise sorting network)เป็นเครือข่ายการเรียงลำดับที่ค้นพบและเผยแพร่โดย Ian Parberry ในปี 1992 ในParallel Processing Letters [ ^{1 ] เครือ}ข่ายการเรียงลำดับแบบคู่มีขนาด (จำนวนตัวเปรียบเทียบ) และความลึกเท่ากับเครือข่าย mergesort แบบคี่-คู่ณ เวลาที่เผยแพร่ เครือข่ายนี้เป็นหนึ่งในเครือข่ายที่รู้จักหลายเครือข่ายที่มีความลึกโดยต้องการตัวเปรียบเทียบและมีความลึก ${\displaystyle O(\log ^{2}n)}$${\displaystyle n(\log n)(\log n-1)/4+n-1}$${\displaystyle (\log n)(\log n+1)/2}$

ขั้นตอนการจัดเรียงที่เครือข่ายนำมาใช้มีดังต่อไปนี้ (โดยยึดหลักศูนย์-หนึ่ง ):

1. เรียงลำดับบิตคู่ที่อยู่ติดกันของข้อมูลอินพุต (ซึ่งตรงกับเลเยอร์แรกของแผนภาพ)
2. จัดเรียงคู่ทั้งหมดตามลำดับตัวอักษรโดยการจัดเรียงบิตคี่และบิตคู่แยกกันแบบเรียกซ้ำ (ซึ่งสอดคล้องกับสามชั้นถัดไปของคอลัมน์ 2+4+8 ในแผนภาพ)
3. จัดเรียงคู่ต่างๆ ตามลำดับจากมากไปน้อยโดยใช้เครือข่ายเฉพาะ (ซึ่งตรงกับชั้นสุดท้ายของแผนภาพ)

เครือข่ายการเรียงลำดับแบบคู่มีความคล้ายคลึงกับ Batcher odd-even mergesort มาก แต่แตกต่างกันในโครงสร้างของการดำเนินการ ในขณะที่ Batcher แบ่ง เรียงลำดับ และผสานลำดับย่อยที่ยาวขึ้นเรื่อยๆ ซ้ำๆ วิธีการเรียงลำดับแบบคู่จะทำการแบ่งย่อยทั้งหมดก่อน จากนั้นจึงผสานทั้งหมดในตอนท้ายในลำดับย้อนกลับ ในบางแอปพลิเคชัน เช่น การเข้ารหัสข้อจำกัดของจำนวนสมาชิก เครือข่ายการเรียงลำดับแบบคู่จะเหนือกว่าเครือข่าย Batcher ^{[ 2 ]}

n ← ความยาวของอาร์เรย์ k ← กำลังสองที่น้อยที่สุด, k ≥ n สำหรับ k/2 ≥ p ≥ 1, p ใน k/2, k/4, k/8, … 4, 2, 1 ทำ(การเปรียบเทียบเหล่านี้สามารถทำพร้อมกันได้) สำหรับ 0 ≤ a < n, a อยู่ในช่วง 0, p*2, p*4, p*6, p*8, p*10, … ทำซ้ำสำหรับ 0 ≤ b < p, b อยู่ในช่วง 0, 1, 2, … p-3, p-2, p-1 ทำซ้ำ i ← a + b j ← a + b + p ถ้า j < n ให้เปรียบเทียบและสลับองค์ประกอบ i และ j จบเงื่อนไขสำหรับ k/2 ≥ q ≥ p*2, q ใน k/2, k/4, k/8, … p*8, p*4, p*2 ให้ทำ(การเปรียบเทียบเหล่านี้สามารถทำพร้อมกันได้) สำหรับ 0 ≤ c < n, c ใน 0, p*2, p*4, p*6, p*8, p*10, … ทำเช่น เดียวกัน สำหรับ 0 ≤ d < p, d ใน 0, 1, 2, … p-3, p-2, p-1 ทำเช่นเดียวกัน i ← c + d + p j ← c + d + q ถ้า j < n ให้เปรียบเทียบและสลับองค์ประกอบ i และ j จบเงื่อนไขทำซ้ำ q ทำซ้ำ p 

• เครือข่ายการจัดเรียง – คลังเก็บหน้าเว็บโดยผู้เขียน

บทความเกี่ยวกับอัลกอริทึมหรือโครงสร้างข้อมูลนี้ ยัง ไม่สมบูรณ์คุณสามารถช่วยวิกิพีเดียได้โดยการเพิ่มข้อมูลที่ขาดหายไป

• วี
• ที
• อี