Arguing my algorithm is correct and within the bounds

Question

I'm working on some algorithms assignments and was asked the following: sort an array in O(n) with elements 'r' or 'w' in place so the 'r's always precede the 'w's. So if the input looks like [w,r,w,r,w,r,w,w], after the algorithm has run the array looks like [r,r,r,w,w,w,w,w].

Conceptually this seemed very clear immediately. I had to use two boundary variables holding the position of the first 'w' element and one for the last 'r' element.

My code looks as follows:

char[] A = new char[] { 'w', 'r', 'w', 'r', 'w', 'r', 'w', 'w' };

int lastRedPosition = A.Length - 1;
int firstWhitePosition = 0;

for (int i = firstWhitePosition ; i < A.Length; i++)
{
    // determine the first red from the right e.g. the lastred, ending at the firstwhite position
    for (int j = lastRedPosition; j > firstWhitePosition; j--)
    {
        if (A[j] == 'r')
        {
            lastRedPosition = j;
            break;
        }
    }

    for (int k = firstWhitePosition; k < lastRedPosition; k++)
    {
        if (A[k] == 'w')
        {
            firstWhitePosition = k;
            break;
        }
    }

    A[firstWhitePosition] = 'r';
    A[lastRedPosition] = 'w';
}

Now I think it runs in O(n), intuitively, despite the nested for loops. This is because of the fact that, all in all, the array gets traversed only once. Since we are keeping track of where we were with the lastRedPosition and firstWhitePosition variable.

I do however find it hard to motivate this more formally, because of the same nested for loops... Could someone give me some pointers into the right directopm?

Answer 1

Isn't this just iteration 1 of quicksort?

You scan from the left until you hit 'w'. Then you scan from the right until you hit 'r'. Then you swap the two elements and continue. You stop when the two scanners come together.

That's O(n).

EDIT: such as:

int i = 0, j = n-1;
while(true){
  while(a[i]=='r' && i<n) i++;
  while(a[j]=='w' && j>0) j--;
  if (i >= j) break;
  swap(a[i], a[j]);
}

Answer 2

The first problem is that your algorithm isn't correct. If there are only 'w's or only 'r's in the array, you still write both, a 'w' and an 'r' to the array at the end of the outer loop.

And in that case, your code will actually take Θ(N²) time. Let's say everything is 'r':

char[] A = new char[] { 'r', 'r', 'r', 'r', 'r', 'r', 'r', 'r' };

int lastRedPosition = A.Length - 1;
int firstWhitePosition = 0;

for (int i = firstWhitePosition ; i < A.Length; i++)
{
    // determine the first red from the right e.g. the lastred, ending at the firstwhite position
    for (int j = lastRedPosition; j > firstWhitePosition; j--)
    {
        if (A[j] == 'r')
        {
            lastRedPosition = j;
            break;
        }
    }

j is A.length - 1 - i now. In the first iteration, it found an 'r' immediately, later, there have been written i 'w's to the last entries of the array and lastRedPosition was the index of the first of these, so except for the first iteration,j` is decremented exactly once.

    for (int k = firstWhitePosition; k < lastRedPosition; k++)
    {
        if (A[k] == 'w')
        {
            firstWhitePosition = k;
            break;
        }
    }

firstWhitePosition is always 0. k is incremented until it becomes lastRedPosition without finding a 'w', so firstWhitePosition is not changed. Thus k is incremented A.length - 1 - i times.

Sum over i for a total of ~N²/2 increments of k.

    A[firstWhitePosition] = 'r';
    A[lastRedPosition] = 'w';
}

You must check whether A[firstWhitePosition] actually is 'w' and A[lastRedPosition] actually 'r'. If not, you're done. And your outer loop should check firstWhitePosition < lastRedPosition.

Answer 3

It is easier to see if you convert your outer loop to a while loop that runs until firstWhitePosition and lastRedPosition meet. It is clear that the two variables together just traverse the array once.

Answer 4

Just because the entire array gets traversed only once does not automatically make it O(n). The fact is, in the least optimal case (which is the definition of big-O), the entire array will actually get traversed twice, the second traversal happening inside the outer loop, making it O(n^2).

If you can guarantee that only r's and w's will be in the array, an O(n) approach would simply be to go through the array once, counting how many r's and w's there are, and then reconstructing the array yourself. This is actually 2 traversals making it O(2n) but conventionally those coefficients are dropped.

Answer 5

Technically, this is O(N); however, from a performance standpoint it is O(2N) meaning that it is in the average case half as fast as could be. That's because your outer loop executes once per element, and your inner loops between them traverse every element, meaning there are twice as many iterations as elements.

You have the right idea, but what if, instead of the outer loop traversing every element, you stopped as soon as you "knew" that all the rs were to the left of all the ws?

To put it another way, you start by scanning from the right end of the array for an r (which should go on the left) and from the left for a w (which should go on the right). If the w is to the left of the w, you should swap them and continue; if, however, your "last r" index is to the left of your "first w" index, you are done and should terminate the entire function. Instead, your current implementation keeps looping (and swapping). This is the inefficiency. I would replace the outer for loop with a while loop as Henry suggests, with the terminating condition being that the last r is to the left of the first w.

Answer 6

1. Go through the array once, count the number of 'r' and 'w', store them as numberR and numberW. Store the non 'r' and non 'w' characters in a StringBuffer called S2.

2. Print numberR 'r's into a new StringBuffer S1. Append S2 to S1. Append numberW of 'w's to the S1.

3. Get the character array from the StringBuffer.

Total Cost: O(n)