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

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

Bitonic sort network with eight inputs.
ประเภท	Sorting algorithm
โครงสร้างข้อมูล	Array
ประสิทธิภาพเมื่อเกิดกรณีแย่ที่สุด	$O(\log ^{2}(n))$ parallel time
ประสิทธิภาพเมื่อเกิดกรณีดีที่สุด	$O(\log ^{2}(n))$ parallel time
ประสิทธิภาพเมื่อเกิดกรณีทั่วไป	$O(\log ^{2}(n))$ parallel time
ปริมาณความต้องการพื้นที่เมื่อเกิดกรณีแย่ที่สุด	$O(n\log ^{2}(n))$ non-parallel time

การเรียงลำดับแบบไบโตนิค หรือ 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 อย่างและอื่น ๆ

x0 และ x1 เรียงตามลำดับจากน้อยไปมากx2 และ x3 เรียงตามลำดับจากมากไปหาน้อย

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

จากขั้นตอนเราจะได้รับลำดับ Bitonic ยาว 8 ซึ่งก็คือ 2, 3, 6, 9, 7, 5, 4, 1

หลังจากนั้นนำมาทำ 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 log²n)

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) <= 1:
        return x
    else: 
        first = bitonic_sort(True, x[:len(x) // 2])
        second = bitonic_sort(False, x[len(x) // 2:])
        return bitonic_merge(up, first + second)

อ้างอิง

H.W. Lang Bitonic sort เก็บถาวร 2017-01-10 ที่ เวย์แบ็กแมชชีนค้นหาเมื่อ 7 พฤษภาคม 2561

John Mellor-Crummy Bitonic Sort ค้นหาเมื่อ 7 พฤษภาคม 2561

Thomas W. Christopher Bitonic Sort ค้นหาเมื่อ 7 พฤษภาคม 2561

geeksforgeeks Bitonic Sort ค้นหาเมื่อ 7 พฤษภาคม 2561