Tuesday, March 1, 2011

Placement - Algorithm to group the balls of the same colour


 You have ‘n’ number of balls of 3 different colours and all are mixed up. Write an algorithm to group the balls of the same colour.(eg.i/p:RBWRBWR o/p:RRRBBWW)


Let ball[1 to n] be the array which contains the color of the n balls which can be either R or B or W.
FNR is the index of the first non red ball and LNW is the index of the last non white ball. i will be a traversing pointer which will move from index next to FNR until it reaches next to LNW.
Step 1: set FNR=1
            do until ball[FNR]!=R
            {
                        FNR=FNR+1
            }
Step 2: set LNW=n
            do until ball[LNW]!=W
            {
                        LNW=LNW-1;
            }
Step 3: set i=FNR
            do until i>LNW
            {
                        if ball[i]=R
                        {
                                    swap ball[i] and ball[FNR]
                                    increment FNR
                        }
                        else if ball[i]=W
                        {
                                    swap ball[i] and ball[LNW]
                                    decrement LNW
                        }
increment i
}