Dutch National Flag (DNF) problem (3-way partitioning)

Posted on by

Given an array A[] consisting 0s, 1s and 2s, write a function that sorts A[]. The functions should put all 0s first, then all 1s and all 2s in last.

Example
Input = {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1};
Output = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}

public static void DNFSort(int a[]){
	int p1 = 0;
	int p2 = 0;
	int p3 = a.length-1;
	
	while(p2 <= p3){
		if(a[p2] == 0){
			swap(a, p2, p1);
			p1++;
			p2++;
		}
		else if(a[p2] == 1){
			p2++;
		}
		else if(a[p2] == 2){
			swap(a, p2, p3);
			p3--;
		}
	}
}