আমাদের তিনটি পয়েন্টার নিতে হবে: low, mid, high। low এবং mid পয়েন্টার শুরুতে রাখুন, এবং high পয়েন্টার দেওয়া অ্যারেতে শেষে পয়েন্ট করবে।
যদি array[mid] = 0, তবে array[mid]-কে array[low]-এর সাথে সোয়াপ করুন এবং উভয় পয়েন্টারই একবার ইনক্রিমেন্ট করুন।
যদি array[mid] = 1, তবে কোনো সোয়াপিং প্রয়োজন নেই। mid পয়েন্টার একবার ইনক্রিমেন্ট করুন।
যদি array[mid] = 2, তবে array[mid]-কে array[high]-এর সাথে সোয়াপ করুন এবং high পয়েন্টার একবার ডিক্রিমেন্ট করুন।
টাইম কমপ্লেক্সিটি − O(N)
উদাহরণ
using System;
namespace ConsoleApplication
{
public class Arrays
{
private void Swap(int[] arr, int pos1, int pos2)
{
int temp = arr[pos1];
arr[pos1] = arr[pos2];
arr[pos2] = temp;
}
public void DutchNationalFlag(int[] arr)
{
int low = 0;
int mid = 0;
int high = arr.Length - 1;
while (mid <= high)
{
if (arr[mid] == 0)
{
Swap(arr, low, mid);
low++;
mid++;
}
else if (arr[mid] == 2)
{
Swap(arr, high, mid);
high--;
}
else
{
mid++;
}
}
}
}
class Program
{
static void Main(string[] args)
{
Arrays a = new Arrays();
int[] arr = { 2, 1, 1, 0, 1, 2, 1, 2, 0, 0, 1 };
a.DutchNationalFlag(arr);
for (int i = 0; i < arr.Length; i++)
{
Console.WriteLine(arr[i]);
}
Console.ReadLine();
}
}
}আউটপুট
0 0 0 0 1 1 1 1 2 2 2