โปรแกรมเรียงลำดับไบโตนิค

การเรียงลำดับแบบไบโตนิค หรือ Bitonic Sort คืออัลกอริทึมการเรียงลำดับที่อิงตามการเปรียบเทียบ ซึ่งสามารถทำงานแบบขนานได้ จะมุ่งเน้นไปที่การแปลงลำดับแบบสุ่มของตัวเลขเป็น ลำดับบิตซิติคที่เพิ่มขึ้น monotonically แล้วลดลง การหมุนของบิตโคสมีลำดับไบโตนิค โดยเฉพาะอย่างยิ่งการเรียงแบบ bitonic สามารถจำลองเป็นประเภทของเครือข่ายการเรียงลำดับได้ ลำดับ unsorted เริ่มต้นเข้าสู่ท่อป้อนเข้าซึ่งชุดของตัวเปรียบเทียบจะสลับรายการสองรายการไปเป็นลำดับที่เพิ่มขึ้นหรือลดลง
=== Bitonic Sequence (ลำดับไบโตนิค) ===
1.ลำดับที่เรียงลำดับตามลำดับที่เพิ่มขึ้นถือว่าเป็น Bitonic และส่วนที่ลดลงจะว่างเปล่า ลำดับการสั่งซื้อลดลงจะถือว่าเป็น Bitonic โดยส่วนที่เพิ่มขึ้นจะว่างเปล่า
2.การหมุน Bitonic Sequence เป็นไบโตนิค
==== การสร้าง Bitonic Sequence ====
เริ่มต้นด้วยการสร้างลำดับบิตonic 4 องค์ประกอบจากลำดับ 2-element ติดต่อกัน พิจารณา 4องค์ประกอบในลำดับ x0, x1, x2, x3 เราจัดเรียง x0 และ x1 ตามลำดับจากน้อยไปมากและ x2 และ x3 เรียงลำดับจากมากไปน้อย จากนั้นเราจะต่อทั้งสองคู่เพื่อสร้างลำดับบิตonic 4 องค์ประกอบ จากนั้นเราจะใช้ลำดับบิตonic 4 องค์ประกอบเรียงกันเรียงลำดับจากน้อยไปหามากเรียงตามลำดับจากมากไปหาน้อย (ใช้ Bitonic Sort) และอื่น ๆ จนกว่าเราจะได้ลำดับ bitonic
==== ตัวอย่าง ====
ขั้นตอนที่1 พิจารณาแต่ละองค์ประกอบ 2 ต่อเนื่องเป็นลำดับ bitonic และใช้การจัดเรียง bitonic ในแต่ละองค์ประกอบคู่ ในขั้นตอนต่อไปให้ใช้ลำดับบิตonic 4 องค์ประกอบ 4 อย่างและอื่น ๆ

ขั้นตอนที่2 สองบิตonic ลำดับ 4 องค์ประกอบ: A (2,6,9,3) และB (4,7,5,1) มีความยาวเปรียบเทียบเป็น 2

หลังจากนั้นนำมาทำ Bitonic Sorting โดย
1.การสร้างลำดับบิตเซอร์ ซึ่งจะกล่าวถึงรายละเอียดในข้างต้น หลังจากขั้นตอนต่อไปคืออาร์เรย์จะกลายเป็น {2, 3, 6, 9, 7, 5, 4, 1}
2.การสร้างลำดับที่เรียงลำดับจากลำดับบิตเซอร์ หลังจากขั้นตอนแรก ครึ่งแรกจะถูกจัดเรียงตามลำดับที่เพิ่มขึ้นและครึ่งหลังถูกจัดเรียงตามลำดับที่ลดลง จะเปรียบเทียบองค์ประกอบแรกของครึ่งแรกกับองค์ประกอบแรกของครึ่งหลัง แล้วองค์ประกอบที่สองของครึ่งแรกกับองค์ประกอบที่สองของครึ่งหลังและอื่น ๆ โดยจะแลกเปลี่ยนถ้าองค์ประกอบครึ่งแรกมีขนาดเล็ก

3.จาก {2, 3, 4, 1, 7, 5, 6, 9} จะสังเกตเห็นว่ามีสองลำดับไบโตนิคของความยาว n / 2 เพื่อให้องค์ประกอบทั้งหมดในลำดับครึ่งแรก {2, 3, 4, 1} มีขนาดเล็กกว่าองค์ประกอบทั้งหมดของลำดับไบโตนิคที่สอง {7, 5, 6, 9}ซึ่งทำซ้ำขั้นตอนเดียวกันภายในสองลำดับไบโตนิคและจะได้รับสี่ลำดับไบโตนิคของความยาว n / 4 ดังนั้นองค์ประกอบทั้งหมดของลำดับ bitonic ซ้ายสุดมีขนาดเล็กและองค์ประกอบทั้งหมดของด้านขวาที่มีขนาดใหญ่ จากอาร์เรย์ {2, 1, 4, 3, 6, 5, 7, 9} ถ้าทำซ้ำขั้นตอนอีกครั้งจะได้ลำดับบิตonic 8 บิตของขนาด n / 8 ซึ่งเป็น 1 เนื่องจากลำดับบิตonic ทั้งหมดนี้ถูกเรียงลำดับและทุกลำดับ bitonic มีองค์ประกอบหนึ่งจะเรียงลำดับได้
=== ความซับซ้อนของเวลา ===
ในการจัดเรียงลำดับความยาว n จากสองลำดับ จะเรียงลำดับของความยาว n / 2 ใช้การเปรียบเทียบ O( log n)
เนื่องจากแต่ละขั้นตอนของเครือข่ายการเรียงลำดับประกอบด้วย n / 2 comparators ดังนั้นการเปรียบเทียบทั้งหมด O(n log2n)
=== Code Python การเรียงลำดับแบบไบโตนิค ===
def bitonic_compare(up, x):
dist = len(x) // 2
for i in range(dist):
if (x[i] > x[i + dist]) == up:
x[i], x[i + dist] = x[i + dist], x[i]
def bitonic_merge(up, x):
if len(x) == 1:
return x
else:
bitonic_compare(up, x)
first = bitonic_merge(up, x[:len(x) // 2])
second = bitonic_merge(up, x[len(x) // 2:])
return first + second
def bitonic_sort(up, x):
if len(x) 
== อ้างอิง ==
H.W. Lang  Bitonic sort ค้นหาเมื่อ 7 พฤษภาคม 2561
John Mellor-Crummy Bitonic Sort ค้นหาเมื่อ 7 พฤษภาคม 2561
Thomas W. Christopher Bitonic Sort ค้นหาเมื่อ 7 พฤษภาคม 2561
geeksforgeeks Bitonic Sort ค้นหาเมื่อ 7 พฤษภาคม 2561
ขั้นตอนวิธีการเรียงลำดับ