বিটোনিক সর্ট হলো একটি প্যারালlel সর্টিং অ্যালগরিদম যা সেরা ইমপ্লিমেন্টেশন এবং হার্ডওয়্যার ও প্যারালেল প্রসেসর অ্যারে-এর সাথে সর্বোত্তম ব্যবহার করার জন্য তৈরি করা হয়েছে।
এটি মার্জ সর্টের তুলনায় সবচেয়ে দক্ষ নয়। কিন্তু প্যারালেল ইমপ্লিমেন্টেশনের জন্য ভালো। এর কারণ হচ্ছে প্রিডিফাইনড কম্পারিজন সিকোয়েন্স যা সর্ট করার ডেটা থেকে স্বাধীন।
বিটোনিক সর্ট কার্যকরভাবে কাজ করার জন্য এলিমেন্টের সংখ্যা নির্দিষ্ট ধরণের হতে হবে অর্থাৎ 2^n অর্ডারের।
বিটোনিক সর্টের একটি প্রধান অংশ হচ্ছে বিটোনিক সিকোয়েন্স যা একটি সিকোয়েন্স যার এলিমেন্টের মান প্রথমে বাড়ে এবং তারপর কমে।
বিটোনিক সিকোয়েন্স হলো একটি অ্যারে arr[0 … (n-1)] যদি 0 থেকে n-1 রেঞ্জে একটি ইনডেক্স i থাকে। যার জন্য arr[i]-এর মান অ্যারেতে সবচেয়ে বড়। অর্থাৎ
arr[0] <= arr[1] … <= arr[i] and arr[i] >= arr[i+1] … >= aar[n-1]
বিটোনিক সিকোয়েন্সের বিশেষ বৈশিষ্ট্য −
বিটোনিক সিকোয়েন্স রোটেট করলে আবার বিটোনিক সিকোয়েন্স হয়।
ক্রমবর্ধমান এবং ক্রমহ্রাসমান অর্ডারের সিকোয়েন্স বিটোনিক সিকোয়েন্স।
বিটোনিক সিকোয়েন্স তৈরি করা
বিটোনিক সিকোয়েন্স তৈরির জন্য, আমরা দুটি সাব-সিকোয়েন্স তৈরি করব, একটি ক্রমবর্ধমান এলিমেন্টের এবং অন্যটি ক্রমহ্রাসমান এলিমেন্টের।
উদাহরণস্বরূপ, একটা সিকোয়েন্স arr[] নিই এবং নিচের সিকোয়েন্সটিকে বিটোনিক সিকোয়েন্স-এ রূপান্তর করি।
arr[] = {3, 4, 1, 9, 2, 7, 5, 6}প্রথমে, আমরা এলিমেন্টগুলো জোড়া করব এবং সেগুলোকে বিটোনিক সিকোয়েন্স-এ রূপান্তর করব যেন একটি ক্রমবর্ধমান এবং অন্যটি ক্রমহ্রাসমান হয়।
আমাদের অ্যারেতে, জোড়া তৈরি করে বিটোনিক সিকোয়েন্স বানাই।
arr[] = {(3, 4), (1, 9), (2, 7), (5, 6)} // বিটোনিক সিকোয়েন্স জোড়া তৈরি...
arr[] = {(3, 4), (9, 1), (2, 7), (6, 5)}তারপর, আমরা এই জোড়াগুলোর জোড়া তৈরি করব। অর্থাৎ ৪ এলিমেন্টের বিটোনিক সিকোয়েন্স এবং ২ দূরত্বের এলিমেন্টগুলো তুলনা করব [অর্থাৎ i with i+2]।
arr[] = {(3, 4, 9, 1), (2, 7, 6, 5)}প্রথম সেটের ক্রমবর্ধমান বিটোনিক তৈরি হবে −
(3, 4, 9, 1) : দু দূরত্বের এলিমেন্ট তুলনা। (3, 1, 9, 4) : এখন পরস্পর সমলগ্ন এলিমেন্ট চেক। (1, 3, 4, 9) -> ক্রমবর্ধমান বিটোনিক সিকোয়েন্স।
দ্বিতীয় সেটের ক্রমহ্রাসমান বিটোনিক তৈরি হবে −
(2, 7, 6, 5) : দু দূরত্বের এলিমেন্ট তুলনা। (6, 7, 2, 5) : এখন পরস্পর সমলগ্ন এলিমেন্ট চেক। (7, 6, 5, 2) -> ক্রমহ্রাসমান বিটোনিক সিকোয়েন্স।
শেষে, আমরা আকার ৮-এর বিটোনিক সিকোয়েন্স পাব।
1, 3, 4, 9, 7, 6, 5, 2
এখন, যেহেতু আমরা বিটোনিক সিকোয়েন্স সম্পর্কে জানি। আমরা বিটোনিক সর্টিং সম্পর্কে জানব।
বিটোনিক সর্টিং
বিটোনিক সিকোয়েন্সকে বিটোনিক সর্টিং দিয়ে সর্ট করতে হবে নিচের স্টেপগুলো অনুসরণ করে −
স্টেপ ১ − বিটোনিক সিকোয়েন্স তৈরি করুন।
স্টেপ ২ − এখন, আমাদের একটি বিটোনিক সিকোয়েন্স আছে যার একটি অংশ ক্রমবর্ধমান এবং অন্যটি ক্রমহ্রাসমান।
স্টেপ ৩ − আমরা দুটি অর্ধেকের প্রথম এলিমেন্টগুলো তুলনা এবং সওয়াপ করব। তারপর দ্বিতীয়, তৃতীয়, চতুর্থ এলিমেন্টগুলো।
স্টেপ ৪ − আমরা সিকোয়েন্সের প্রতিটি দ্বিতীয় এলিমেন্ট তুলনা এবং সওয়াপ করব।
স্টেপ ৫ − সর্বশেষে, আমরা পরস্পর সমলগ্ন এলিমেন্টগুলো তুলনা এবং সওয়াপ করব।
স্টেপ ৬ − সব সওয়াপের পর, আমরা সর্টেড অ্যারে পাব।
উদাহরণ
বিটোনিক সর্ট ইমপ্লিমেন্টেশন দেখানোর প্রোগ্রাম −
#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
