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]);
}