Dutch National Flag Problem

I added code about this problem in this post. In this article, I mainly add more pictures to help understanding the analysis/thinking process of this question. When beginners could understand the whole process of this problem, they would improve greatly in using pointers, indexes and edges in an array.

We can divide an array into four parts – Negative, Zero, Unknown, and Positive. This aims at analyzing swap and switch pointers when necessary. This is also a kind of method to analyze problem — stay in an particular intermediate state and then go further starting from this state.

Assue that the front, i, and back — three pointers point to three positions respectively. What positions? as the following picture show, they point to the positions immediately after/before the boundary between Negative and Zero, Zero and Unknown, and Unknown and Positive. Pretty straightforward when looking at the picture.

 

National Flag pointers

 

 

When i(the index points to unknown part) is found to be a zero, we should merge this “zero” into the zero part of array, and then move i points to next element in the unknown part.

When i is found to be a negative number, we need to swap this “negative” number with the first zero which is pointed by front, so that both “negative” and “zero” part remain unchanged. After swapping, we need move both front and i one step afterward, so that they remain pointing to the boundaries.

When i is found to be a positive number, the same with the previous situation, just swap this “positive” number with what back points to ( array[back] ), and then move back one step forward.Here needs pay attention, since we don’t know the number i points to after swapping is negative/positive/zero, we need remain i unchanged for next round checking.

Now, we are almost done, so when we need stop? Yes, when the length of unknown part is zero, at that time, i meets k, then we finish the while loop.

I like this question very much, since this method solve the problem using O(n). I cannot think any other methods better than this one, since I could come up with O(n^2), even O(n^3). But none wins over this method.

 

Emma Y.Guo

1/18/2013 8:58 AM

@Seattle

 

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>