#include <iostream>
using namespace std;
void DutchNationalFlag4(int * arr , int n )
{
int low = 0 , mid1 = 0 , mid2 = n- 1 , high = n-1 ;
int temp;
// This type of problems are best solved by using invariants
// arr[ 0 .. low -1 ] conatins 0
// arr[ low .. mid1 -1 ] contains 1
// arr[ mid1 .. mid2 ] is unknown
// arr[ mid2 + 1 ... high - 1 ] contains 2
// arr[ high .. n-1 ] contains 3
// termination condition : Evert Iteration unkown length decreases so eventually will be Zero
while( mid1 <= mid2 )
{
switch( arr[ mid1 ])
{
case 0 :
{
std::swap( arr[ low ] , arr [ mid1 ] );
low ++ ;
mid1 ++;
break;
}
case 1 :
{
mid1 ++;
break;
}
case 2 :
{
std::swap( arr[ mid1 ] , arr[ mid2 ]);
mid2 -- ;
break;
}
case 3 :
{
std::swap( arr[ mid1 ] , arr[ mid2 ]);
std::swap( arr[ mid2 ] , arr[ high ]);
mid2 --;
high --;
break;
}
}
}
for( int i =0 ; i < n ; i++)
{
cout << arr[ i ] << " " ;
}
}
int main() {
int arr[] = {1,2,3,0,2,1,3,0,2,1,0,1,3,1,0,2,1,0};
int n = sizeof(arr) / sizeof(arr[0]) ;
DutchNationalFlag4(arr , n );
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKCnZvaWQgRHV0Y2hOYXRpb25hbEZsYWc0KGludCAqIGFyciAsIGludCBuICkKewoJaW50IGxvdyA9IDAgLCBtaWQxID0gMCAsIG1pZDIgPSBuLSAxICwgaGlnaCA9IG4tMSA7CglpbnQgdGVtcDsKCQoJLy8gVGhpcyB0eXBlIG9mIHByb2JsZW1zIGFyZSBiZXN0IHNvbHZlZCBieSB1c2luZyBpbnZhcmlhbnRzIAoJCgkvLyBhcnJbIDAgLi4gbG93IC0xIF0gY29uYXRpbnMgMAoJLy8gYXJyWyBsb3cgLi4gbWlkMSAtMSBdIGNvbnRhaW5zIDEKCS8vIGFyclsgbWlkMSAuLiBtaWQyIF0gaXMgdW5rbm93bgoJLy8gYXJyWyBtaWQyICsgMSAuLi4gaGlnaCAtIDEgXSBjb250YWlucyAyCgkvLyBhcnJbIGhpZ2ggLi4gbi0xIF0gY29udGFpbnMgMwoJCgkvLyB0ZXJtaW5hdGlvbiBjb25kaXRpb24gOiBFdmVydCBJdGVyYXRpb24gdW5rb3duIGxlbmd0aCBkZWNyZWFzZXMgc28gZXZlbnR1YWxseSB3aWxsIGJlIFplcm8KCXdoaWxlKCBtaWQxIDw9IG1pZDIgKQoJewoJCXN3aXRjaCggYXJyWyBtaWQxIF0pCgkJewoJCQljYXNlIDAgOgoJCQl7CgkJCQlzdGQ6OnN3YXAoIGFyclsgbG93IF0gLCBhcnIgWyBtaWQxIF0gKTsKCQkJCWxvdyArKyA7CgkJCQltaWQxICsrOwoJCQkJYnJlYWs7CgkJCX0KCQkJCgkJCWNhc2UgMSA6CgkJCXsKCQkJCW1pZDEgKys7CgkJCQlicmVhazsKCQkJfQoJCQkKCQkJY2FzZSAyIDoKCQkJewoJCQkJc3RkOjpzd2FwKCBhcnJbIG1pZDEgXSAsIGFyclsgbWlkMiBdKTsKCQkJCW1pZDIgLS0gOwoJCQkJYnJlYWs7CgkJCX0KCQkJCgkJCWNhc2UgMyA6CgkJCXsKCQkJCXN0ZDo6c3dhcCggYXJyWyBtaWQxIF0gLCBhcnJbIG1pZDIgXSk7CgkJCQlzdGQ6OnN3YXAoIGFyclsgbWlkMiBdICwgYXJyWyBoaWdoIF0pOwoJCQkJbWlkMiAtLTsKCQkJCWhpZ2ggLS07CgkJCQlicmVhazsKCQkJfQoJCQkJCgkJfQoJfQoJCglmb3IoIGludCBpID0wIDsgaSA8IG4gOyBpKyspCgl7CgkJY291dCA8PCBhcnJbIGkgXSA8PCAiICIgOwoJfQp9CgppbnQgbWFpbigpIHsKCWludCBhcnJbXSA9IHsxLDIsMywwLDIsMSwzLDAsMiwxLDAsMSwzLDEsMCwyLDEsMH07CglpbnQgbiA9IHNpemVvZihhcnIpIC8gc2l6ZW9mKGFyclswXSkgOwoJRHV0Y2hOYXRpb25hbEZsYWc0KGFyciAsIG4gKTsKCXJldHVybiAwOwp9