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

จากวิกิพีเดีย สารานุกรมเสรี
ไปยังการนำทาง ไปยังการค้นหา
โปรแกรมเรียงลำดับไบโตนิค
bitonic sort network with eight inputs
Bitonic sort network with eight inputs.
ประเภทSorting algorithm
โครงสร้างข้อมูลArray
ประสิทธิภาพเมื่อเกิดกรณีแย่ที่สุด parallel time
ประสิทธิภาพเมื่อเกิดกรณีดีที่สุด parallel time
ประสิทธิภาพเมื่อเกิดกรณีทั่วไป parallel time
ปริมาณความต้องการพื้นที่เมื่อเกิดกรณีแย่ที่สุด 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 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) <= 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ค้นหาเมื่อ 7 พฤษภาคม 2561

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

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

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