Question is from here:

A famous problem given by Edsgar Dijkstra is to sort an array of red, white and blue symbols so that all reds come together, followed by all whites, followed finally by all blues; it’s called the Dutch National Flag problem because the Dutch flag consists of three stripes with red at the top, blue at the bottom, and white in the middle. You are allowed to scan through the array only once, and the only operations permitted are to examine the color of the symbol at a given array location and to swap the symbols at two locations.

Your task is to write a program to perform the sort given above.

Solution:

import java.util.ArrayList;

public class Dutch_National_Flag {
	public static void main(String[] args) {
		//test cases
		String [] s = {"R","R","W","B","R","R","R"};
		String [] s1 = {"B", "W", "B", "R", "W", "R", "B"};
		flagIt(s);
		flagIt(s1);
	}
	
	private static void flagIt(String[] s) {
		int redIndex = 0, blueIndex = 0, whiteIndex = 0;
		//storing result 
		ArrayList<String> res = new ArrayList<String>();

		for (int i = 0; i < s.length; i++) {
			if(s[i].equals("R")) {
				res.add(redIndex, s[i]);
				redIndex++;
				blueIndex++;
				whiteIndex++;
			} else if (s[i].equals("W")) {
				res.add(whiteIndex, s[i]);
				whiteIndex++;
				blueIndex++;
			} else {
				res.add(blueIndex, s[i]);
				blueIndex++;
			}
		}
		System.out.println(res);
	}
}

Output:

[R, R, R, R, R, W, B]
[R, R, W, W, B, B, B]