## Sort n elements, each of which is red, white, or blue on the color in the order Red, White, Blue.

Skiena : 4-18. Suppose an array *A* consists of *n* elements, each of which is *red*, *white*, or *blue*. We seek to sort the elements so that all the *reds* come before all the *whites*, which come before all the *blues*The only operation permitted on the keys are

*Examine(A,i)*— report the color of the*i*th element of*A*.*Swap(A,i,j)*— swap the*i*th element of*A*with the*j*th element.

Find a correct and efficient algorithm for red-white-blue sorting. There is a linear-time solution. This is also known as the Dutch national flag problem. The simplest linear time solution performs two passes of the partition operation from Quicksort. The first pass treats the red and white elements as indistinguishable, and separates them from the blue. The second pass is just separates the elements within the red/white sub-array.

Solution:

i1 <—-Red —> i2 j1 <——–White ——-> j2 k1 <——-Blue ——-> k2 NEXT

In some already sorted list, i1 is the index of first red, i2 = last red index, j1 = first white index, j2 = last white index, k1=first blue and k2 = last blue.

now, the algorithm would be

if ( NEXT == Blue) {NEXT ++; k2++}; if (NEXT == White) { swap(Elements[k1],Elements[NEXT];j2++;k1++;k2++;} if ( NEXT == Red) { swap(Elements[k1],Elements[NEXT]); swap(Elements[k1],Elements[j1]); i2++;j1++;j2++;k1++;k2++}

for initial value assume all values i1=i2=j1=j2=k1=k2 = 0;

Bingo, this is O(n) complexity algorithm.

Incredible. That was a good read. I will social bookmark this website for later.

I like your style.

You actually make it seem so easy with your presentation but I find this topic to be really something which I think I would

never understand. It seems too complicated and extremely broad for me.

I am looking forward for your next post, I’ll try to get the hang of it!

Great code 🙂