জাভা ব্যবহার করে 0, 1 এবং 2 এর অ্যারে সাজান

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' হয়, তাহলে মিড পয়েন্টার বাড়ান।

উদাহরণ

public class Solution {
   public static void binarySorting(int arr[], int n){
      int low=0;
      int high= n-1;
      int mid=0;
      while(mid<=high){
         if(arr[mid]==0){
            int temp= arr[mid];
            arr[mid]= arr[low];
            arr[low]= temp;
            mid++;
            low++;
         }
         if(arr[mid]==1){
            mid++;
         }
         if(arr[mid]==2){
            int temp= arr[mid];
            arr[mid]= arr[high];
            arr[high]= temp;
            high--;
         }
      }
   }
   public static void print(int arr[], int n){
      for (int i = 0; i < n; i++)
         System.out.print(arr[i] +" ");
   }
   public static void main(String[] args){
      int arr[] ={ 0,0,1,0,1,0,1,2,2};
      int n = arr.length;
      binarySorting(arr, n);
      print(arr, n);
   }
}

আউটপুট

উপরের কোডটি চালানোর ফলে আউটপুট তৈরি হবে,

0 0 0 0 1 1 1 1 2