myUsFlagSort

FlagSorts.java

	private static void checkMyUsFlagSortInput(int[] input, int red, int white) {
		if (input.length < 4) {
			throw new IllegalArgumentException("the min input size is 4");
		}
		if (input.length % 2 != 0) {
			throw new IllegalArgumentException("the input size " + input.length + " is wrong");
		}
		int redCount = 0;
		int whiteCount = 0;
		for (int elem : input) {
			if (elem == white) {
				whiteCount++;
			} else if (elem == red) {
				redCount++;
			} else {
				throw new IllegalArgumentException("illegal element: " + elem);
			}
		}
		if (redCount != whiteCount) {
			throw new IllegalArgumentException("the number of red and white elements must be equal. " + "red count="
					+ redCount + " whiteCount=" + whiteCount);
		}
	}

	public static void myUsFlagSort(int[] input, int red, int white) {
		checkMyUsFlagSortInput(input, red, white);
		// Input: 1, 2, 1, 1, 1, 2, 2, 2
		// Output: 1, 1, 2, 2, 1, 1, 2, 2

		// Let 1 be red
		// Let 2 be white

		// Red stripes are at 0, 1, 4, 5 ...
		int redIndex = 0;

		// White stripes are at 2, 3, 6, 7 ...
		int whiteIndex = 2;

		while (redIndex < input.length && whiteIndex < input.length) {
			if (input[redIndex] == red) {
				redIndex = getNewRedIndex(redIndex);
			} else {
				if (input[whiteIndex] == red) {
					Utils.swap(input, redIndex, whiteIndex);
					redIndex = getNewRedIndex(redIndex);
				}
				if (whiteIndex % 2 == 0) {
					whiteIndex++;
				} else {
					whiteIndex += 3;
				}
			}
		}
	}

Utils.java

public class Utils {

	private Utils() {
		throw new AssertionError();
	}

	public static void swap(int[] input, int index1, int index2) {
		int temp = input[index1];
		input[index1] = input[index2];
		input[index2] = temp;
	}
}