Return to Answer

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.

The simplest 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.

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.

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.

The simplest 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).

A more complicated but faster on is 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.

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.

The simplest 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.

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.

To avoid these problems, walk in from both ends simultaneously instead of scanning only from left-to-right. This allows you to pick the better swap and do it only when necessary.

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.

The simplest 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).

A more complicated but faster on is 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.