Sort RGB

This problem was asked by Google.

Given an array of strictly the characters 'R', 'G', and 'B', segregate the values of the array so that all the Rs come first, the G's come second, and the B's come last. You can only swap elements of the array.

Do this in linear time and in-place.

For example, given the array ['G', 'B', 'R', 'R', 'B', 'R', 'G'], it should become ['R', 'R', 'R', 'G', 'G', 'B', 'B'].

Explanation:

In this problem we are not allowed to use extra space so we have to do in-place sorting.

Means we have to swap the elements to sort.

Now if we can sort R and B such that all R's are in the front part of array and all B are in the back of the array so all G will be automatically sorted and that will give us our desired array in sorted R,G and B form respectively.

Program:

li = ['R', 'R', 'R', 'R', 'G', 'G', 'G', 'B', 'B', 'B', 'B']
n = len(li)
index = 0
index_of_R = 0
index_of_B = n-1

while index<=index_of_B:
 if li[index]=='R':
        li[index] = li[index_of_R]
        li[index_of_R] = 'R'
        index_of_R +=1
        index+=1

 elif li[index]=='B':
        li[index] = li[index_of_B]
        li[index_of_B] = 'B'
        index_of_B-=1
 
 else:
        index+=1

print(li)

Happy Coding!

Follow us on Instagram @programmersdoor

Join us on Telegram @programmersdoor

Please write comments if you find any bug in the above code/algorithm, or find other ways to solve the same problem.

Follow Programmers Door for more.

#blog #interview #placement #learn #computer #science