การเรียงลำดับบิตโทนิกคืออัลกอริธึมการเรียงลำดับแบบขนานที่สร้างขึ้นเพื่อการใช้งานที่ดีที่สุดและมีการใช้งานที่เหมาะสมกับฮาร์ดแวร์และอาร์เรย์ตัวประมวลผลแบบขนาน .
ไม่ใช่วิธีที่มีประสิทธิภาพมากที่สุดเมื่อเทียบกับการเรียงลำดับการผสาน แต่เป็นการดีสำหรับการใช้งานแบบคู่ขนาน นี่เป็นเพราะลำดับการเปรียบเทียบที่กำหนดไว้ล่วงหน้าซึ่งทำให้การเปรียบเทียบเป็นอิสระจากข้อมูลที่จะจัดเรียง
เพื่อให้การจัดเรียงแบบ bitonic ทำงานได้อย่างมีประสิทธิภาพ จำนวนองค์ประกอบควรอยู่ในประเภทปริมาณเฉพาะ เช่น ลำดับ 2^n .
ส่วนสำคัญอย่างหนึ่งของการเรียงลำดับบิตโทนิกคือลำดับบิตโทนิกซึ่งเป็นลำดับที่องค์ประกอบมีค่า เพิ่มครั้งแรก แล้ว ลดลง .
ซีเควนซ์ไบโทนิค เป็นอาร์เรย์ arr[0 … (n-1)] หากมีค่าดัชนี i ภายในช่วง 0 ถึง n-1 ซึ่งค่าของ arr[i] จะมากที่สุดในอาร์เรย์ กล่าวคือ
arr[0] <= arr[1] … <= arr[i] and arr[i] >= arr[i+1] … >= aar[n-1]
ลักษณะพิเศษของลำดับบิโตนิก −
-
ลำดับ Bitonic สามารถหมุนกลับไปเป็นลำดับ bitonic ได้
-
ลำดับที่มีองค์ประกอบในลำดับที่เพิ่มขึ้นและลดลงคือลำดับบิตโทนิก
การสร้างลำดับบิตโทนิก
สำหรับการสร้างลำดับบิตโทนิก เราจะสร้างสองลำดับย่อย หนึ่งมีองค์ประกอบจากน้อยไปมาก และอีกส่วนหนึ่งมีองค์ประกอบจากมากไปหาน้อย
ตัวอย่างเช่น มาดูลำดับ arr[] และแปลงลำดับต่อไปนี้เป็นลำดับบิตโทนิก
arr[] = {3, 4, 1, 9, 2, 7, 5, 6} ขั้นแรก เราจะสร้างคู่ขององค์ประกอบ และจากนั้นสร้างลำดับบิตโทนิกของสิ่งเหล่านี้ในลักษณะที่หนึ่งอยู่ในลำดับจากน้อยไปมาก และอีกส่วนหนึ่งอยู่ในลำดับจากมากไปหาน้อยเป็นต้น
สำหรับอาร์เรย์ของเรา มาสร้างคู่ในลำดับบิตโทนิก
arr[] = {(3, 4), (1, 9), (2, 7), (5, 6)}
// creating bitonic sequence pairs…
arr[] = {(3, 4), (9, 1), (2, 7), (6, 5)} จากนั้นเราจะสร้างคู่ของคู่เหล่านี้ นั่นคือ 4 องค์ประกอบตามลำดับบิโตนิกและเปรียบเทียบองค์ประกอบที่มีระยะทาง 2 [เช่น ฉันกับ i+2].
arr[] = {(3, 4, 9, 1), (2, 7, 6, 5)} บิตโทนิกจากน้อยไปมากในชุดแรกจะถูกสร้างขึ้นเป็น -
(3, 4, 9, 1) : comparing two distant elements. (3, 1, 9, 4) : Now, check adjacent elements. (1, 3, 4, 9) -> ascending bitonic sequence.
บิตโทนิกจากมากไปน้อยในชุดที่สองจะถูกสร้างขึ้นเป็น -
(2, 7, 6, 5) : comparing two distant elements. (6, 7, 2, 5) : Now, check adjacent elements. (7, 6, 5, 2) -> descending bitonic sequence.
ในตอนท้ายจะได้ลำดับ bitonic ขนาด 8
1, 3, 4, 9, 7, 6, 5, 2
ตอนนี้ เนื่องจากเราได้เรียนรู้เกี่ยวกับลำดับบิโตนิกแล้ว เราจะรู้เกี่ยวกับ Bitonic Sorting .
การจัดเรียงแบบไบโทนิค
ในการเรียงลำดับลำดับบิตโทนิกโดยใช้การเรียงลำดับบิตโทนิกโดยใช้ขั้นตอนเหล่านี้ -
ขั้นตอนที่ 1 − สร้างลำดับบิตโทนิก
ขั้นตอนที่ 2 − ตอนนี้ เรามีลำดับบิตโทนิกโดยส่วนหนึ่งอยู่ในลำดับที่เพิ่มขึ้นและส่วนอื่นๆ อยู่ในลำดับที่ลดลง
ขั้นตอนที่ 3 − เราจะเปรียบเทียบและสลับองค์ประกอบแรกของทั้งสองส่วน จากนั้นองค์ประกอบที่สอง สาม สี่สำหรับพวกเขา
ขั้นตอนที่ 4 − เราจะเปรียบเทียบและสลับองค์ประกอบทุก ๆ วินาทีของลำดับ
ขั้นตอนที่ 5 − ในที่สุด เราจะเปรียบเทียบและสลับองค์ประกอบที่อยู่ติดกันของลำดับ
ขั้นตอนที่ 6 − หลังจากสลับทั้งหมดแล้ว เราจะได้อาร์เรย์ที่จัดเรียง
ตัวอย่าง
โปรแกรมแสดงการใช้งาน Bitonic Sort −
#include<iostream>
using namespace std;
void bitonicSeqMerge(int a[], int start, int BseqSize, int direction) {
if (BseqSize>1){
int k = BseqSize/2;
for (int i=start; i<start+k; i++)
if (direction==(a[i]>a[i+k]))
swap(a[i],a[i+k]);
bitonicSeqMerge(a, start, k, direction);
bitonicSeqMerge(a, start+k, k, direction);
}
}
void bitonicSortrec(int a[],int start, int BseqSize, int direction) {
if (BseqSize>1){
int k = BseqSize/2;
bitonicSortrec(a, start, k, 1);
bitonicSortrec(a, start+k, k, 0);
bitonicSeqMerge(a,start, BseqSize, direction);
}
}
void bitonicSort(int a[], int size, int up) {
bitonicSortrec(a, 0, size, up);
}
int main() {
int a[]= {5, 10, 51, 8, 1, 9, 6, 22};
int size = sizeof(a)/sizeof(a[0]);
printf("Original array: \n");
for (int i=0; i<size; i++)
printf("%d\t", a[i]);
bitonicSort(a, size, 1);
printf("\nSorted array: \n");
for (int i=0; i<size; i++)
printf("%d\t", a[i]);
return 0;
} ผลลัพธ์
Original array: 5 10 51 8 1 9 6 22 Sorted array: 1 5 6 8 9 10 22 51
