russianFlagProblem

RussianFlagProblem.java

	public static void russianFlagProblem(int[] input, int red, int white, int blue) {
		// input: 1, 2, 3, 1, 1, 2, 3, 1, 1
		// Dutch: 1, 1, 1, 1, 1, 2, 2, 3, 3

		// (1 - red, 2 - white, 3 - blue)

		// Russian: 2 - white, 3 - blue, 1 - red
		// output: 2, 2, 3, 3, 1, 1, 1, 1, 1

		int i = 0; // the end of the white region (exclusive)
		int j = 0; // the current element
		int k = input.length - 1; // the start of the blue region (exclusive)

		while (j <= k) {
			if (input[j] == white) {
				Utils.swap(input, j++, i++);
			} else if (input[j] == red) {
				Utils.swap(input, j, k--);
			} else {
				j++;
			}
		}
	}