DutchNationalFlagProblem

Problem :

Given an array consisting of 0's 1's 2's ( Red, Blue and Green ). Come up with an approach where in array is rearranged such that, all 0's appear first followed by 1's and then 2's.

Solution :

This is equivalent to the partitioning having pivot element as 1. All elements less than 1( which is 0) will appear on the left hand side and all elements >1 are appearing on the right hand side. ( 2)

Here is the attached code for the same.

	import java.util.Random;
	public class DutchFlagProblem {
	private int[] array;
	public void setLength(int length) {
	array = new int[length];
	}
	public int[] getArray() {
	return array;
	}
	public void rearrangeOddEven() {
	setLength(10);
	int[] array = getArray();
	Random random = new Random();
	for (int i = 0; i < array.length; i++) {
	array[i] = random.nextInt(9);
	}
	int low = 0, high = array.length - 1;
	while (low < high) {
	while (array[low] % 2 == 0 && low < high)
	low++;
	while (array[high] % 2 == 1 && low < high)
	high--;
	if (low < high) {
	swap(low, high);
	low++;
	high--;
	}
	}
	displayArray();
	}
	private void swap(int low, int high) {
	int temp;
	temp = array[low];
	array[low] = array[high];
	array[high] = temp;
	}
	public void rearrangeZeroOneTwo() {
	setLength(100);
	int[] array = getArray();
	Random random = new Random();
	for (int i = 0; i < array.length; i++) {
	array[i] = random.nextInt(3);
	}
	displayArray();
	int posZero = 0, posTwo = array.length - 1, i = 0;
	while (i < array.length) {
	if (array[i] == 0) {
	array[i] = array[posZero];
	array[posZero] = 0;
	posZero++;
	} else if (array[i] == 2 && i < posTwo) {
	array[i] = array[posTwo];
	array[posTwo] = 2;
	posTwo--;
	i--;
	}
	i++;
	}
	displayArray();
	}
	private void displayArray() {
	for (int i = 0; i < array.length; i++) {
	System.out.println("Element is " + array[i]);
	}
	}
	public static void main(String[] args) {
	DutchFlagProblem dutchFlagProblem = new DutchFlagProblem();
	dutchFlagProblem.rearrangeOddEven();
	dutchFlagProblem.rearrangeZeroOneTwo();
	}
	}

view raw DutchNationalFlag.java hosted with ❤ by GitHub