ভিন্ন নাটস এবং অন্য একটি বোল্ট-এর লিস্ট দেওয়া আছে। আমাদের কাজ প্রদত্ত লিস্ট থেকে নাটস এবং বোল্ট-এর সঠিক মিল বের করা, এবং মিল পাওয়া গেলে নাটটিকে বোল্ট দিয়ে অ্যাসাইন করা।
এই সমস্যাটি কুইক-সোর্ট কৌশল দিয়ে সমাধান করা হয়। বোল্টের শেষ এলিমেন্টকে পিভট হিসেবে নিয়ে, নাটস লিস্ট রি-অ্যারেঞ্জ করুন এবং সেই নাটের চূড়ান্ত পজিশন পান যার বোল্টটি পিভট এলিমেন্ট। নাটস লিস্ট পার্টিশন করার পর, নির্বাচিত নাট ব্যবহার করে বোল্টস লিস্ট পার্টিশন করুন। একই কাজ বাম ও ডান সাব-লিস্টের জন্য করে সব মিল পাওয়া যায়।
ইনপুট এবং আউটপুট
ইনপুট: লক এবং কী-এর লিস্ট। nuts = { ),@,*,^,(,%, !,$,&,#} bolts = { !, (, #, %, ), ^, &, *, $, @ } আউটপুট: নাটস এবং বোল্ট মিলানোর পর: Nuts: ! # $ % & ( ) * @ ^ Bolts: ! # $ % & ( ) * @ ^অ্যালগরিদম
partition(array, low, high, pivot)
ইনপুট: একটি অ্যারে, লো এবং হাই ইনডেক্স, পিভট এলিমেন্ট।
আউটপুট: পিভট এলিমেন্টের চূড়ান্ত লোকেশন।
শুরু
i := low
j low থেকে high রেঞ্জে, করুন
যদি array[j] < pivot, তবে
array[i] এবং array[j] সোয়াপ করুন
i ১ বাড়ান
অন্যথায় যদি array[j] = pivot, তবে
array[j] এবং array[high] সোয়াপ করুন
j ১ কমান
শেষ
array[i] এবং array[high] সোয়াপ করুন
i ফেরত দিন
শেষnutAndBoltMatch(nuts, bolts, low, high)
ইনপুট: নাটস লিস্ট, বোল্টস লিস্ট, অ্যারে-এর নিচের এবং উপরের ইনডেক্স।
আউটপুট: কোন নাট কোন বোল্ট জন্য তা প্রদর্শন করুন।
শুরু pivotLoc := partition(nuts, low, high, bolts[high]) partition(bolts, low, high, nuts[pivotLoc]) nutAndBoltMatch(nuts, bolts, low, pivotLoc-1) nutAndBoltMatch(nuts, bolts, pivotLoc + 1, high) শেষ
উদাহরণ
#include<iostream> using namespace std; void show(char array[], int n) { for(int i = 0; i<n; i++) cout << array[i] << " "; } int partition(char array[], int low, int high, char pivot) { //কুইক সোর্টের জন্য পিভট লোকেশন বের করুন int i = low; for(int j = low; j<high; j++) { if(array[j] <pivot) { //যদি j-তম এলিমেন্ট পিভট থেকে কম, i এবং j সোয়াপ করুন swap(array[i], array[j]); i++; }else if(array[j] == pivot) { //যদি j-তম এলিমেন্ট পিভটের মতো, j-তম এবং শেষ এলিমেন্ট সোয়াপ করুন swap(array[j], array[high]); j--; } } swap(array[i], array[high]); return i; //পিভট এলিমেন্টের লোকেশন } void nutAndBoltMatch(char nuts[], char bolts[], int low, int high) { if(low < high) { int pivotLoc = partition(nuts, low, high, bolts[high]); //বোল্ট থেকে পিভট বেছে নিতে নাট পার্টিশনিং partition(bolts, low, high, nuts[pivotLoc]); //পূর্বের পিভট লোকেশন বোল্টেও রাখুন nutAndBoltMatch(nuts, bolts, low, pivotLoc - 1); nutAndBoltMatch(nuts, bolts, pivotLoc+1, high); } } int main() { char nuts[] = {')','@','*','^','(','%','!','$','&','#'}; char bolts[] = {'!','(','#','%',')','^','&','*','$','@'}; int n = 10; nutAndBoltMatch(nuts, bolts, 0, n-1); cout << "After matching nuts and bolts:"<< endl; cout << "Nuts: "; show(nuts, n); cout << endl; cout << "Bolts: "; show(bolts, n); cout << endl; }আউটপুট
After matching nuts and bolts: Nuts: ! # $ % & ( ) * @ ^ Bolts: ! # $ % & ( ) * @ ^
