Sort on second key when, first key in a set is sorted

Assume that we are given as input n pairs of items, where
  1. the first item is a number
  2. 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).

1 comment:

Madhur Kumar Tanwani said...

Solution :
1.> Iterate over the set.
2.> Store each element in a key-ordered look up table.
a.> the key being a function of the color
b.> the key order is such that red < blue < yellow
c.> the value is a list of the set's elements
3.> If the value for a set element is already present, simply append the set element to the value list and continue
4.> After all elements have been iterated over, simply iterate over the ordered key set and print the value list

Step 2b, could be a doubly linked list implementation, restricting the complexity to O(n)

Overall time complexity would also be O(n)