A character array of arbitary length with 'R', 'B', 'W' is needed to be sorted in that order

Question

There is a char array of n length. The array can have elements only from any order of R, B, W. You need to sort the array so that order should R,B,W (i.e. all R will come first followed by B and then W).

Constraints: Time complexity is O(n) and space complexity should be O(1).

Assumption: You can assume one swap method is given with signature swap(char[] arr, int index1, int index2) that swaps number in unit time. Method given to implement: public sort(char[]array);

Here is my implementation of it. A better solution from anyone is appreciated. Anyone is free to point out any mistakes.

public static void sort(char[] arr){
     int rIndex = 0, wIndex = arr.length -1;
     for (int i = 0 ; i <= wIndex;){
         if ( arr[i] == 'R' ){
             swap(arr, i , rIndex ++ );
             i ++;
         } else if (arr[i] == 'W' ){
             swap(arr, i , wIndex -- );
         }else{
            i ++;
         }
     }
}

Answer 1

Don't bother swapping. Just do a counting sort!

public static void sort(char[] arr) {
    // Count occurrences of each letter
    int r = 0, b = 0, w = 0;
    for (char c : arr) {
        switch (c) {
          case 'R': r++; break;
          case 'B': b++; break;
          case 'W': w++; break;
          default: throw new IllegalArgumentException();
        }
    }

    // Write out the appropriate repetitions of each letter
    int i = 0;
    while (r-- > 0) arr[i++] = 'R';
    while (b-- > 0) arr[i++] = 'B';
    while (w-- > 0) arr[i++] = 'W';
}

Not only is the code easy to understand, it's also gentle to the cache since you always proceed linearly down the array.

Answer 2

One quick improvement to your solution would be to use switch(arr[i]) instead of the if-else chain.

The only real problem I see beyond the complexity and non-obviousness of the algorithm is that it can end up doing a lot of unnecessary swaps--often in-place. While swap could be written to avoid them, you still pay the cost of the function call.

Another solution is to do it in two passes: first pull all Rs to the left and then all Ws to the right. While it takes twice as long, it's still equivalent to O(n).

public static void sort(char[] arr) {
    int length = arr.length;
    int rIndex = 0, wIndex = length - 1;
    for (int i = 0; i < length; i++) {
        if (arr[i] == 'R') {
            if (i != rIndex) {
                swap(arr, i, rIndex);
            }
            ++rIndex;
        }
    }
    for (int i = length - 1; i >= 0; i--) {
        if (arr[i] == 'W') {
            if (i != wIndex) {
                swap(arr, i, wIndex);
            }
            --wIndex;
        }
    }
}

A more complicated but possibly faster solution would be to walk in from both ends simultaneously instead of scanning from left-to-right. This allows you to pick the better swap and do it only when necessary. I started on it, but it quickly got out of hand.

Answer 3

Basically this is near as good as you can get it.

I would simply suggest

• renaming of index variables to clarify their function
• adding a comment that clarifies the algorithm
• use a switch as it yield a clearer structure in this instance.

(note that i've also fiddled with the place of indices to be able to more elegantly formulate the invariants)

public static void sort(char[] arr) {
    // invariants :
    //   * each index up to and including lastR contains 'R'
    //   * each index equal to or greater than firstW contains 'W'
    //   * each index greater than lastR but smaller than i contains B
    //   array will be sorted once i == firstW
    int lastR = -1, firstW = arr.length;
    for (int i = 0; i < firstW; ) {
        switch(arr[i]) {
            case 'R':
                swap(arr, i, ++lastR);
                i++;
                break;
            case 'W':
                swap(arr, i, --firstW);
                break;
            default:
                i++;
        }
    }
}

Answer 4

You can convert the characters to an order number, and implement a regular sorting algorithm. That way you only need to solve converting the character to a order number, and can use a proven algorithm for the rest.

Here is an example using bubble sort, but you can of course use a more efficient sorting algorithm.

public static int convert(char c) {
  switch (c) {
    case 'R': return 0;
    case 'B': return 1;
    default: return 2;
  }
}

public static void sort(char[] arr){
  int cont = true;
  while (cont) {
    cont = false;
    for (int i = 1; i < arr.length; i++) {
      if (convert(arr[i - 1]) > convert(arr[i])){
        swap(arr, i - 1, i);
        cont = true;
      }
    }
  }
}