The Algorithm Design Manual Problem 4-4

Assume that we are given n pairs of items as input, where the first item is a
number and the second item is one of three colors (red, blue, or yellow). Further
assume that the items are sorted by number. Give an O(n) algorithm to sort the
items by color (all reds before all blues before all yellows) such that the numbers
for identical colors stay sorted.
For example: (1,blue), (3,red), (4,blue), (6,yellow), (9,red) should become (3,red),
(9,red), (1,blue), (4,blue), (6,yellow)
.

package avdongre.tadm;

import java.util.ArrayList;
import java.util.List;

public class ColorSort {
	private enum Color {
		RED, BLUE, YELLOW
	}

	private class Pair {
		public int first;
		public Color second;

		public Pair(int x, Color y) {
			first = x;
			second = y;
		}

		@Override
		public String toString() {
			return String.format(first + "," + second);
		}
	}

	public List<Pair> colorSortRedBlueYello(List<Pair> input) {
		if (input == null) {
			return null;
		}
		// This is special case or similar to Dutch national flag problem.
		int left = 0;
		int mid = 0;
		int right = input.size() - 1;

		while (mid <= right) {
			switch (input.get(mid).second) {
			case RED: {
				Pair temp = input.get(left);
				input.set(left, input.get(mid));
				input.set(mid, temp);
				left++;
				mid++;
				break;
			}
			case BLUE:
				mid++;
				break;
			case YELLOW: {
				Pair temp = input.get(mid);
				input.set(mid, input.get(right));
				input.set(right, temp);
				right--;

				break;
			}
			}
		}
		return input;
	}

	private List<Pair> generateInput() {
		List<Pair> lp = new ArrayList<Pair>();

		lp.add(new Pair(1, Color.BLUE));
		lp.add(new Pair(3, Color.RED));
		lp.add(new Pair(4, Color.BLUE));
		lp.add(new Pair(6, Color.YELLOW));
		lp.add(new Pair(9, Color.RED));

		return lp;
	}

	public static void main(String args[]) {
		ColorSort cs = new ColorSort();
		List<Pair> input = cs.generateInput();
		cs.colorSortRedBlueYello(input);
		System.out.println(input);
		
	}
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s