০, ১ এবং ২ সম্বলিত একটি অ্যারে দেওয়া থাকলে, সেটিকে এমনভাবে সর্ট করতে হবে যাতে সব ০ প্রথমে আসে, তারপর ১ এবং সবশেষে ২। এই সমস্যাটি ইন-প্লেস (in-place) সমাধান করতে হবে।
এটি সমাধানের জন্য DNF (Dutch National Flag) সর্টিং অ্যালগরিদম ব্যবহার করা হয়।
ইনপুট-১: arr[] = {2,0,0,1,2,1}
আউটপুট: 0 0 1 1 2 2
ব্যাখ্যা: DNF অ্যালগরিদম ব্যবহার করে ০, ১, ২ সর্ট করলে আউটপুট হবে {0,0,1,1,2,2}।
ইনপুট-২: arr[] = {0,1,1,2,1,1,0}
আউটপুট: 0 0 1 1 1 1 2
সমাধানের পদ্ধতি
DNF সর্টিং অ্যালগরিদমে তিনটি পয়েন্টার (low, mid, high) ব্যবহার করে অ্যারেটি ট্রাভার্স করা হয় এবং প্রয়োজনীয় এলিমেন্টগুলো সোয়াপ করা হয়।
low পয়েন্টার অ্যারের শুরুতে, high পয়েন্টার শেষে রাখা হয়।
mid পয়েন্টার অ্যারের শুরু থেকে শেষ পর্যন্ত ইটারেট করে।
যদি
arr[mid] == 0হয়, তবেarr[low]এর সাথে সোয়াপ করেlowএবংmidউভয়েই ইনক্রিমেন্ট করা হয়।যদি
arr[mid] == 2হয়, তবেarr[high]এর সাথে সোয়াপ করেhighডিক্রিমেন্ট এবংmidইনক্রিমেন্ট করা হয়।যদি
arr[mid] == 1হয়, তবে শুধুmidইনক্রিমেন্ট করা হয়।
জাভা কোড উদাহরণ
public class Solution {
public static void dnfSort(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++;
} else if (arr[mid] == 1) {
mid++;
} else { // arr[mid] == 2
int temp = arr[mid];
arr[mid] = arr[high];
arr[high] = temp;
high--;
}
}
}
public static void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
public static void main(String[] args) {
int arr[] = {0, 0, 1, 0, 1, 0, 1, 2, 2};
int n = arr.length;
dnfSort(arr, n);
printArray(arr, n);
}
}
আউটপুট
0 0 0 0 1 1 1 1 2 2
