Algorithms
Dutch National Flag (DNF) problem (3-way partitioning)
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--;
}
}
}