हमें थ्री-पॉइंटर्स लेने की जरूरत है, लो, मिड, हाई। हम शुरुआत में निम्न और मध्य बिंदुओं का उपयोग करेंगे, और उच्च सूचक दिए गए सरणी के अंत में इंगित करेंगे।
यदि सरणी [मध्य] =0 है, तो सरणी [मध्य] को सरणी [निम्न] के साथ स्वैप करें और दोनों पॉइंटर्स को एक बार बढ़ाएं।
यदि सरणी [मध्य] =1 है, तो कोई अदला-बदली की आवश्यकता नहीं है। मध्य सूचक को एक बार बढ़ाएँ।
यदि सरणी [मध्य] =2, तो हम सरणी [मध्य] को सरणी [उच्च] के साथ स्वैप करते हैं और उच्च सूचक को एक बार घटाते हैं।
समय जटिलता - 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