DNF_Sort.cpp

// Name: JHALA DEVRAJSINH SHRIPALSINH
// Date: 01/07/2021
// Purpose: Dutch National Flag (DNF) Sort
// Approach:
// Check the value of arr[mid]:
// if 0, swap arr[low] and arr[mid], low++, mid++
// if 1, mid++
// if 2, swap arr[mid] and arr[high], high--

// Time complexity:
// O(N) because in each operation, either mid gets incremented or high gets decremented


#include<bits/stdc++.h>
using namespace std;

void swap(int arr[], int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}


void DNF_Sort(int arr[], int n)
{
    int low = 0;
    int mid = 0;
    int high = n - 1;

    while(mid <= high)
    {
        if(arr[mid] == 0)
        {
            swap(arr,low,mid);
            low++; mid++;
        }

        else if(arr[mid] == 1)
        {
            mid++;
        }

        else
        {
            swap(arr,mid,high);
            high--;
        }
    }
}



int main()
{

    int arr[] = {1,0,2,1,0,1,2,1,2};
    DNF_Sort(arr,9);

    for(int i=0;i<9;i++)
    {
        cout << arr[i] << " ";
    }

    return 0;
}