Algorithms

Question

Given ‘N’ objects, which are coloured as red, white and blue. Sort these

objects so that objects of the same colour are adjacent, with the colours

in the order red, white and blue. Design an algorithm with a time com-

plexity of O(nlog n)

Comments

@Karthi2003

put red =0, white = 1, blue = 2 and then apply merge sort….you will get O(nlgn).

If you use counting sort then the time complexity will be reduced to O(n).

Answer 1

Can be done in O(N) complexity, programmatically.

Considering an array is given where Red object is denoted as 0, White object is denoted as 1 and Blue object is denoted as 2.

Now, taking 3 variables count the number of 0s, 1s and 2s in each variable.

• red_count = Number of 0s
• white_count = Number of 1s
• blue_count = Number of 2s

Then at last,

• First assign ‘0’ red_count times in the array.
• Then assign ‘1’ white_count times in the array.
• Then assign ‘2’ blue_count times in the array.

Ex – 

Array = [1,0,1,2,0,1,2,1,2,0,1,2]

red_count = 3, white_count = 5, blue_count=4

Modified Array will be = [0,0,0,1,1,1,1,1,2,2,2,2].