সি++ এ বিটোনিক সাজান

বিটোনিক সর্ট হল একটি সমান্তরাল সাজানোর অ্যালগরিদম যা সর্বোত্তম বাস্তবায়নের জন্য তৈরি করা হয়েছে এবং হার্ডওয়্যার এবং সমান্তরাল প্রসেসর অ্যারে সহ সর্বোত্তম ব্যবহার রয়েছে .

মার্জ সাজানোর তুলনায় এটি সবচেয়ে কার্যকর নয়। তবে এটি সমান্তরাল বাস্তবায়নের জন্য ভাল। এটি পূর্বনির্ধারিত তুলনা অনুক্রমের কারণে যা তুলনাগুলিকে সাজানো ডেটা থেকে স্বাধীন করে।

বাইটোনিক সাজানোর জন্য কার্যকরভাবে কাজ করার জন্য উপাদানের সংখ্যা একটি নির্দিষ্ট ধরনের পরিমাণে হওয়া উচিত অর্থাৎ অর্ডার 2^n .

বিটোনিক সাজানোর একটি প্রধান অংশ হল বিটোনিক ক্রম যা একটি ক্রম যার উপাদানগুলির মান প্রথমে বৃদ্ধি পায় এবং তারপর হ্রাস .

বাইটোনিক সিকোয়েন্স যদি 0 থেকে n-1 রেঞ্জের মধ্যে একটি সূচক মান i থাকে তবে এটি একটি অ্যারে অ্যারে[0 … (n-1)]। যার জন্য অ্যারেতে arr[i] এর মান সবচেয়ে বেশি। অর্থাৎ

arr[0] <=arr[1] … <=arr[i] এবং 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)}

তারপর, আমরা এই জোড়া জোড়া তৈরি করব। অর্থাৎ 4টি উপাদান বিটোনিক সিকোয়েন্স এবং উপাদানগুলির সাথে তুলনা করুন একটি 2 দূরত্ব [অর্থাৎ i এর সাথে 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) -> অবরোহী বিটোনিক ক্রম। 

 শেষে, আমরা সাইজ 8 এর বিটোনিক সিকোয়েন্স পাব।
 
1, 3, 4, 9, 7, 6, 5, 2
 

 এখন, যেহেতু আমরা বিটোনিক সিকোয়েন্স সম্পর্কে শিখেছি। আমরা বাইটোনিক বাছাই সম্পর্কে জানব .
 
বাইটোনিক বাছাই
 

 এই ধাপগুলি ব্যবহার করে বিটোনিক বাছাই ব্যবহার করে একটি বিটোনিক ক্রম সাজাতে -
 

 ধাপ 1 - একটি বিটোনিক ক্রম তৈরি করুন৷
৷ 

 ধাপ 2 − এখন, আমাদের একটি বাইটোনিক সিকোয়েন্স আছে যার একটি অংশ ক্রমবর্ধমান ক্রমে এবং অন্যটি হ্রাস ক্রমে।
 

 ধাপ 3 − আমরা উভয় অর্ধের প্রথম উপাদানের তুলনা ও অদলবদল করব। তারপর তাদের জন্য দ্বিতীয়, তৃতীয়, চতুর্থ উপাদান।
 

 পদক্ষেপ 4৷ − আমরা তুলনা করব এবং অদলবদল করব, অনুক্রমের প্রতিটি দ্বিতীয় উপাদান।
 

 ধাপ 5 − পরিশেষে, আমরা তুলনা করব এবং অনুক্রমের সন্নিহিত উপাদানগুলিকে অদলবদল করব।
 

 ধাপ 6 − সমস্ত অদলবদল করার পরে, আমরা সাজানো অ্যারে পাব।
 
উদাহরণ
 

 বিটোনিক সাজানোর বাস্তবায়ন দেখানোর জন্য প্রোগ্রাম -
 
#includeনেমস্পেস ব্যবহার করে std;void bitonicSeqMerge(int a[], int start, int BseqSize, int direction) { if (BseqSize>1){ int k =BseqSize/2; জন্য (int i=start; ia[i+k])) swap(a[i],a[i+k]); bitonicSeqMerge (a, start, k, দিক); bitonicSeqMerge(a, start+k, k, দিকনির্দেশ); }} 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, দিকনির্দেশ); }} 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("মূল অ্যারে:\ n"); জন্য (int i=0; i 
আউটপুট
 
মূল অ্যারে:5 10 51 8 1 9 6 22 সাজানো অ্যারে:1 5 6 8 9 10 22 51