0, 1 এবং 2 এর একটি অ্যারে দেওয়া, উপাদানগুলিকে এমন ক্রমে সাজান যাতে সমস্ত শূন্য 1 এর আগে এবং সমস্ত 2 এর শেষে আসে। আমাদের অ্যারের সমস্ত উপাদানকে ইন-প্লেস করতে হবে।
আমরা DNF (Dutch National Flag) Sorting Algorithm ব্যবহার করে এই সমস্যার সমাধান করতে পারি। উদাহরণস্বরূপ,
ইনপুট-1 −
arr[ ]= {2,0,0,1,2,1 } আউটপুট −
0 0 1 1 2 2
ব্যাখ্যা − DNF সর্টিং অ্যালগরিদম ব্যবহার করে 0,1 এবং 2 ধারণকারী উপাদানগুলির প্রদত্ত অ্যারে সাজান, এটি আউটপুটটিকে {0,0,1,1,2,2} হিসাবে প্রিন্ট করবে৷
ইনপুট-2 −
arr[ ]= {0,1,1,2,1,1,0} আউটপুট −
0 0 1 1 1 1 2
ব্যাখ্যা − DNF সর্টিং অ্যালগরিদম ব্যবহার করে 0,1 এবং 2 ধারণকারী উপাদানগুলির প্রদত্ত অ্যারে সাজানো, এটি আউটপুটটিকে {0,0,1,1,1,1,2} হিসাবে প্রিন্ট করবে৷
এই সমস্যা সমাধানের পদ্ধতি
0, 1 এবং 2 এর প্রদত্ত অ্যারেতে, আমরা DNF সাজানোর অ্যালগরিদম ব্যবহার করতে পারি।
DNF সাজানোর অ্যালগরিদম − অ্যালগরিদমের প্রয়োজনীয় উপাদানগুলি অদলবদল করে অ্যারে জুড়ে পুনরাবৃত্তি করার জন্য 3টি পয়েন্টার প্রয়োজন৷
-
অ্যারের শুরুতে একটি নিম্ন পয়েন্টার এবং অ্যারের শেষে উচ্চ পয়েন্টার নির্দেশক তৈরি করুন৷
-
অ্যারের মিডপয়েন্ট খুঁজুন এবং একটি মিড পয়েন্টার তৈরি করুন যা অ্যারের শুরু থেকে শেষ পর্যন্ত পুনরাবৃত্তি করে।
-
যদি অ্যারের মধ্য-পয়েন্টার '0' হয়, তাহলে নিম্নে নির্দেশিত উপাদানটিকে অদলবদল করুন। নিম্ন পয়েন্টার এবং মিড পয়েন্টার বৃদ্ধি করুন।
-
যদি অ্যারের মধ্য-পয়েন্টারটি '2' হয়, তাহলে উচ্চে নির্দেশিত উপাদানটির সাথে এটি অদলবদল করুন। মিড পয়েন্টার বাড়ান এবং হাই পয়েন্টার কমিয়ে দিন।
-
যদি অ্যারের মিড-পয়েন্টার '1' হয়, তাহলে মিড পয়েন্টার বাড়ান।
উদাহরণ
#include<iostream>
using namespace std;
void dnfsort(int a[], int n){
int low= 0;
int high= n-1;
int mid=0;
while(mid<=high){
if(a[mid]==0){
swap(a[mid],a[low]);
mid++;
low++;
}
if(a[mid]==1){
mid++;
}
if(a[mid]==2){
swap(a[mid],a[high]);
high--;
}
}
}
int main(){
int a[]= {1,0,0,2,1,1,0,0,1};
int n= sizeof(a)/sizeof(int);
dnfsort(a,n);
for(int i=0;i<n;i++){
cout<<a[i]<<" ";
}
return 0;
} আউটপুট
উপরের কোডটি চালানোর ফলে আউটপুট তৈরি হবে,
0 0 0 0 1 1 1 1 2
