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\$
7
  • \$\begingroup\$ Does this work? Running it in my head with "WRB" gives "RWB". \$\endgroup\$ Sep 28, 2013 at 18:03
  • \$\begingroup\$ It will give RBW for sure. \$\endgroup\$
    – MohdAdnan
    Sep 28, 2013 at 18:05
  • \$\begingroup\$ Ah, I missed the i <= wIndex termination. \$\endgroup\$ Sep 28, 2013 at 18:11
  • \$\begingroup\$ Using the actual code on "WBRWBRBWRB" yields "RRBRBBBWWW". \$\endgroup\$ Sep 28, 2013 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\$ Sep 28, 2013 at 19:24

4 Answers 4

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\$
3
  • \$\begingroup\$ complexity is needed to be O(1). \$\endgroup\$
    – MohdAdnan
    Sep 29, 2013 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, 2013 at 12:23
  • \$\begingroup\$ Yes I actually meant time complexity O(n) \$\endgroup\$
    – MohdAdnan
    Sep 29, 2013 at 12:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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