CareerCup

This probably isn't the most efficient, but it was the first thing that came to mind. It could also be cleaned up a bit.

The algorithm works by creating pointers to the first and last elements of an array. It moves the pointers towards the middle, until one half of the array is sorted. If this occurs, we implicitly know the other half is sorted.

Worst case is O(n), where n is the number of balls.

public class SortBalls {
	public static void main(String[] args) {
		final char redBall = 'R';
		final char blackBall = 'B';
		
		System.out.println("Unsorted Array Test:");
		char[] ballsToSort = {redBall, redBall, blackBall, redBall, blackBall, blackBall, redBall, blackBall, redBall, blackBall};
		sort(ballsToSort, redBall);
		
		for (int i = 0; i < ballsToSort.length; i++) {
			System.out.println(ballsToSort[i]);
		}
		
		System.out.println("Sorted Array Test:");
		ballsToSort = new char[] {redBall, redBall, redBall, redBall, redBall, blackBall, blackBall, blackBall, blackBall, blackBall};
		sort(ballsToSort, redBall);
		
		for (int i = 0; i < ballsToSort.length; i++) {
			System.out.println(ballsToSort[i]);
		}
		
		System.out.println("Empty Array Test:");
		ballsToSort = new char[0];
		sort(ballsToSort, redBall);
		
		for (int i = 0; i < ballsToSort.length; i++) {
			System.out.println(ballsToSort[i]);
		}
		
	}
	
	public static void sort(char[] a, char firstBallType) {
		// Pointers to the left and right halves of the array
		int left = 0;
		int right = a.length - 1;
		
		while (left < (a.length / 2) && right >= (a.length /2)) {
			
			if (a[left] == firstBallType) {	
				// Left ball was in the correct order
				left++;
			}
			else {
				if (a[right] == firstBallType) {
					// Need to swap left and right balls
					char leftBall = a[left];
					a[left] = a[right];
					a[right] = leftBall;
					
					left++;
					right--;
				}
				else {
					right--;
				}
			}
		}
	}
}

start from 0 and find first black index
start from n-1 and find first red index
then swap these black and red.
continue till these two index meet each other.

public static void sort(String [] st){
		int n = st.length;
		int b=0;//black Index
		int r=n-1;//red Index
		while(b<r){
			while(b<n-1 && !st[b].equalsIgnoreCase("B"))
				b++;
			while(r>0 && !st[r].equalsIgnoreCase("R"))
				r--;
			if(b<r){
				String temp = st[b];
				st[b] = st[r];
				st[r] = temp;
			}
		}
	}

The efficient solution with complexity of O(n+2) as follows,

public static void sortR(String [] st){
int n = st.length;
int countR=0;
int countB=0;
String[][] arr=new String[2][5];

for(int index=0;index<st.length;index++){
if(st[index].equalsIgnoreCase("R")){
if(countR<5){
arr[0][countR]=st[index];
countR++;
}
}else {
if(countB<5){
arr[1][countB]=st[index];
countB++;
}

}
}
countR=0;
countB=0;
for(int index=0;index<st.length;index++){

if(countR<5){
st[index]= arr[0][countR];
countR++;
}

else if(countB<5){
st[index]=arr[1][countB];
countB++;
}


}

}

The efficient solution with complexity of O(n+2) as follows,

public static void sortR(String [] st){
        int n = st.length;
        int   countR=0;
        int   countB=0;
        String[][] arr=new String[2][5];
        
         for(int index=0;index<st.length;index++){
             if(st[index].equalsIgnoreCase("R")){
                 if(countR<5){
                arr[0][countR]=st[index];
                 countR++;
                 }
             }else {
                 if(countB<5){
                 arr[1][countB]=st[index]; 
                 countB++;
                 }
                 
             }
         }
         countR=0;
         countB=0;
         for(int index=0;index<st.length;index++){
            
                 if(countR<5){
                     st[index]= arr[0][countR];
                 countR++;
                 }
           
                 else if(countB<5){
                     st[index]=arr[1][countB]; 
                 countB++;
                 }
                 
             
         }
   
    }

A simplified approach would be to use logic similar to an iteration of quick sort. pick up the last ball and start comparison from start, if ball is red swap else just increment.