C++-এ DNF অ্যালগরিদম দিয়ে ০, ১, ২ সর্ট করা

০, ১ এবং ২ মান ধারণকারী একটি অ্যারেকে সর্ট করতে হবে যাতে সব ০ আগে, তারপর ১ এবং সবশেষে ২ থাকে। এটি ইন-প্লেস সর্টিং করতে হবে। DNF (Dutch National Flag) সর্টিং অ্যালগরিদম এই কাজের জন্য উপযুক্ত।

ইনপুট-১

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

আউটপুট

0 0 1 1 2 2

ইনপুট-২

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

আউটপুট

0 0 1 1 1 1 2

DNF সর্টিং অ্যালগরিদম

এই অ্যালগরিদমে তিনটি পয়েন্টার ব্যবহার করা হয়: low, mid, high।

• low অ্যারের শুরুতে, high শেষে এবং mid শুরুতে থাকে।
• যদি arr[mid] == 0 হয়, তবে arr[low]-এর সাথে সোয়্যাপ করে low++ এবং mid++ করুন।
• যদি arr[mid] == 1 হয়, শুধু mid++ করুন।
• যদি arr[mid] == 2 হয়, arr[high]-এর সাথে সোয়্যাপ করে high-- করুন।
• mid <= high পর্যন্ত লুপ চালান।

উদাহরণ

#include <iostream>
using namespace std;

void dnfSort(int a[], int n) {
    int low = 0, high = n - 1, mid = 0;
    while (mid <= high) {
        if (a[mid] == 0) {
            swap(a[mid], a[low]);
            mid++; low++;
        } else if (a[mid] == 1) {
            mid++;
        } else 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