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' है, तो मध्य सूचक को बढ़ाएँ।
उदाहरण
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