Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
การเรียงลำดับแบบไบโตนิค หรือ Bitonic Sort คืออัลกอริทึมการเรียงลำดับที่อิงตามการเปรียบเทียบ ซึ่งสามารถทำงานแบบขนานได้ จะมุ่งเน้นไปที่การแปลงลำดับแบบสุ่มของตัวเลขเป็น ลำดับบิตซิติคที่เพิ่มขึ้น monotonically แล้วลดลง การหมุนของบิตโคสมีลำดับไบโตนิค โดยเฉพาะอย่างยิ่งการเรียงแบบ bitonic สามารถจำลองเป็นประเภทของเครือข่ายการเรียงลำดับได้ ลำดับ unsorted เริ่มต้นเข้าสู่ท่อป้อนเข้าซึ่งชุดของตัวเปรียบเทียบจะสลับรายการสองรายการไปเป็นลำดับที่เพิ่มขึ้นหรือลดลง
 Bitonic sort network with eight inputs. | |
| ประเภท | Sorting algorithm |
|---|---|
| โครงสร้างข้อมูล | |
| ประสิทธิภาพเมื่อเกิดกรณีแย่ที่สุด | parallel time |
| ประสิทธิภาพเมื่อเกิดกรณีดีที่สุด | parallel time |
| ประสิทธิภาพเมื่อเกิดกรณีทั่วไป | parallel time |
| ปริมาณความต้องการพื้นที่เมื่อเกิดกรณีแย่ที่สุด | non-parallel time |
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) <= 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
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
kareriyngladbaebbibotnikh hrux Bitonic Sort khuxxlkxrithumkareriyngladbthixingtamkarepriybethiyb sungsamarththanganaebbkhnanid camungennipthikaraeplngladbaebbsumkhxngtwelkhepn ladbbitsitikhthiephimkhun monotonically aelwldlng karhmunkhxngbitokhsmiladbibotnikh odyechphaaxyangyingkareriyngaebb bitonic samarthcalxngepnpraephthkhxngekhruxkhaykareriyngladbid ladb unsorted erimtnekhasuthxpxnekhasungchudkhxngtwepriybethiybcaslbraykarsxngraykaripepnladbthiephimkhunhruxldlngopraekrmeriyngladbibotnikhBitonic sort network with eight inputs praephthSorting algorithmokhrngsrangkhxmulprasiththiphaphemuxekidkrniaeythisudO log2 n displaystyle O log 2 n parallel timeprasiththiphaphemuxekidkrnidithisudO log2 n displaystyle O log 2 n parallel timeprasiththiphaphemuxekidkrnithwipO log2 n displaystyle O log 2 n parallel timeprimankhwamtxngkarphunthiemuxekidkrniaeythisudO nlog2 n displaystyle O n log 2 n non parallel timek Bitonic Sequence ladbibotnikh 1 ladbthieriyngladbtamladbthiephimkhunthuxwaepn Bitonic aelaswnthildlngcawangepla ladbkarsngsuxldlngcathuxwaepn Bitonic odyswnthiephimkhuncawangepla 2 karhmun Bitonic Sequence epnibotnikh karsrang Bitonic Sequence erimtndwykarsrangladbbitonic 4 xngkhprakxbcakladb 2 element tidtxkn phicarna 4xngkhprakxbinladb x0 x1 x2 x3 eracderiyng x0 aela x1 tamladbcaknxyipmakaela x2 aela x3 eriyngladbcakmakipnxy caknneracatxthngsxngkhuephuxsrangladbbitonic 4 xngkhprakxb caknneracaichladbbitonic 4 xngkhprakxberiyngkneriyngladbcaknxyiphamakeriyngtamladbcakmakiphanxy ich Bitonic Sort aelaxun cnkwaeracaidladb bitonic twxyang khntxnthi1 phicarnaaetlaxngkhprakxb 2 txenuxngepnladb bitonic aelaichkarcderiyng bitonic inaetlaxngkhprakxbkhu inkhntxntxipihichladbbitonic 4 xngkhprakxb 4 xyangaelaxun x0 aela x1 eriyngtamladbcaknxyipmakx2 aela x3 eriyngtamladbcakmakiphanxy khntxnthi2 sxngbitonic ladb 4 xngkhprakxb A 2 6 9 3 aelaB 4 7 5 1 mikhwamyawepriybethiybepn 2 cakkhntxneracaidrbladb Bitonic yaw 8 sungkkhux 2 3 6 9 7 5 4 1 hlngcaknnnamatha Bitonic Sorting ody 1 karsrangladbbitesxr sungcaklawthungraylaexiydinkhangtn hlngcakkhntxntxipkhuxxarerycaklayepn 2 3 6 9 7 5 4 1 2 karsrangladbthieriyngladbcakladbbitesxr hlngcakkhntxnaerk khrungaerkcathukcderiyngtamladbthiephimkhunaelakhrunghlngthukcderiyngtamladbthildlng caepriybethiybxngkhprakxbaerkkhxngkhrungaerkkbxngkhprakxbaerkkhxngkhrunghlng aelwxngkhprakxbthisxngkhxngkhrungaerkkbxngkhprakxbthisxngkhxngkhrunghlngaelaxun odycaaelkepliynthaxngkhprakxbkhrungaerkmikhnadelk cakkhntxndngklawkcaidibotnikhthieriyngladbaelw 3 cak 2 3 4 1 7 5 6 9 casngektehnwamisxngladbibotnikhkhxngkhwamyaw n 2 ephuxihxngkhprakxbthnghmdinladbkhrungaerk 2 3 4 1 mikhnadelkkwaxngkhprakxbthnghmdkhxngladbibotnikhthisxng 7 5 6 9 sungthasakhntxnediywknphayinsxngladbibotnikhaelacaidrbsiladbibotnikhkhxngkhwamyaw n 4 dngnnxngkhprakxbthnghmdkhxngladb bitonic saysudmikhnadelkaelaxngkhprakxbthnghmdkhxngdankhwathimikhnadihy cakxarery 2 1 4 3 6 5 7 9 thathasakhntxnxikkhrngcaidladbbitonic 8 bitkhxngkhnad n 8 sungepn 1 enuxngcakladbbitonic thnghmdnithukeriyngladbaelathukladb bitonic mixngkhprakxbhnungcaeriyngladbid khwamsbsxnkhxngewla inkarcderiyngladbkhwamyaw n caksxngladb caeriyngladbkhxngkhwamyaw n 2 ichkarepriybethiyb O log n enuxngcakaetlakhntxnkhxngekhruxkhaykareriyngladbprakxbdwy n 2 comparators dngnnkarepriybethiybthnghmd O n log2n Code Python kareriyngladbaebbibotnikh def bitonic compare up x dist len x 2 for i in range dist if x i gt 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 lt 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 xangxingH W Lang Bitonic sort 2017 01 10 thi ewyaebkaemchchinkhnhaemux 7 phvsphakhm 2561 John Mellor Crummy Bitonic Sort khnhaemux 7 phvsphakhm 2561 Thomas W Christopher Bitonic Sort khnhaemux 7 phvsphakhm 2561 geeksforgeeks Bitonic Sort khnhaemux 7 phvsphakhm 2561