C++ का उपयोग करके 0, 1 और 2 की सरणी को सॉर्ट करें

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} प्रिंट करेगा।

इनपुट-2 -

arr[] = {0, 1, 1, 2, 1, 1, 0}

आउटपुट -

0 0 1 1 1 1 2

व्याख्या - DNF सॉर्टिंग एल्गोरिदम का उपयोग करके 0, 1 और 2 वाले दिए गए सरणी के तत्वों को सॉर्ट करने पर, यह आउटपुट के रूप में {0, 0, 1, 1, 1, 1, 2} प्रिंट करेगा।

इस प्रॉब्लम को हल करने का दृष्टिकोण

दिए गए 0, 1 और 2 की सरणी में, हम DNF सॉर्टिंग एल्गोरिदम का उपयोग कर सकते हैं।

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