myUsFlagSort

MyUsFlagSort.java

	public static void myUsFlagSort(int[] input, int stripeLen, int red, int 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) {
					swap(input, redIndex, whiteIndex);
					redIndex = getNewRedIndex(redIndex);
				}
				if (whiteIndex % 2 == 0) {
					whiteIndex++;
				} else {
					whiteIndex += 3;
				}
			}
		}
	}