0, 1, और 2 की एक सरणी को देखते हुए, तत्वों को इस क्रम में क्रमबद्ध करें कि सभी शून्य पहले 1 से पहले और सभी 2 अंत में आएं। हमें सरणी के सभी तत्वों को जगह में क्रमबद्ध करना होगा।
हम डीएनएफ (डच राष्ट्रीय ध्वज) सॉर्टिंग एल्गोरिदम का उपयोग करके इस समस्या को हल कर सकते हैं। उदाहरण के लिए,
इनपुट-1 -
arr[ ]= {2,0,0,1,2,1 } आउटपुट -
0 0 1 1 2 2
स्पष्टीकरण - डीएनएफ सॉर्टिंग एल्गोरिदम का उपयोग करके 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
स्पष्टीकरण - डीएनएफ सॉर्टिंग एल्गोरिदम का उपयोग करके 0,1 और 2 वाले तत्वों की दी गई सरणी को सॉर्ट करना, यह आउटपुट को {0,0,1,1,1,1,2} के रूप में प्रिंट करेगा।
इस समस्या को हल करने का तरीका
0, 1 और 2 के दिए गए सरणी में, हम 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