6
\$\begingroup\$

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 ++;
         }
     }
}
\$\endgroup\$
  • \$\begingroup\$ Does this work? Running it in my head with "WRB" gives "RWB". \$\endgroup\$ – David Harkness Sep 28 '13 at 18:03
  • \$\begingroup\$ It will give RBW for sure. \$\endgroup\$ – MohdAdnan Sep 28 '13 at 18:05
  • \$\begingroup\$ Ah, I missed the i <= wIndex termination. \$\endgroup\$ – David Harkness Sep 28 '13 at 18:11
  • \$\begingroup\$ Using the actual code on "WBRWBRBWRB" yields "RRBRBBBWWW". \$\endgroup\$ – David Harkness Sep 28 '13 at 18:22
  • 1
    \$\begingroup\$ Editing the code in place makes it hard to discuss as it invalidates all the comments and possibly answers. This looks about as good as you'll get it I think. \$\endgroup\$ – David Harkness Sep 28 '13 at 19:24
8
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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++;
        }
    }
}
\$\endgroup\$
0
\$\begingroup\$

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;
      }
    }
  }
}
\$\endgroup\$
  • \$\begingroup\$ complexity is needed to be O(1). \$\endgroup\$ – MohdAdnan Sep 29 '13 at 12:13
  • \$\begingroup\$ @MohdAdnan: Sorry, I missed that part. The space complexity actually is O(1), but the time complexity isn't O(n). \$\endgroup\$ – Guffa Sep 29 '13 at 12:23
  • \$\begingroup\$ Yes I actually meant time complexity O(n) \$\endgroup\$ – MohdAdnan Sep 29 '13 at 12:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.