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