Dutch National Flag Algorithm

Sort_an_array_of_0s_1s+and_2s.cpp

// Credits : Ashmik Harinkhede
#include<iostream>
#include<vector>
using namespace std;

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

void dutchFlagSort(vector<int> &arr){

    // all elements coming before index low are 0 and all elements coming after index high are 2
    // all elements >= low and < i  are 1

    int low = 0, high = arr.size() - 1;
    for(int i = 0; i <= high;){
        if (arr[i] == 0){
            swap(arr, i, low);
            i++;
            low++;
        } else if (arr[i] == 1){
            i++;
        } else{ // the case for arr[i] == 2
            swap(arr,i,high);
            // decrement 'high' only , after swap the number at index i could be 0 , 1 or 2
            high--;
        }
    }
}

int main(){

    vector<int> arr = {1,0,2,1,0};
    dutchFlagSort(arr);
    for(auto num : arr)
        cout << num << " ";

    cout << endl;

    return 0;
}