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

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 bluesThe only operation permitted on the keys are

  1. Examine(A,i) — report the color of the ith element of A.
  2. Swap(A,i,j) — swap the ith element of A with the jth 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.

Advertisements
Categories: algorithm
  1. June 23, 2013 at 6:38 pm

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

  2. July 12, 2013 at 6:12 am

    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!

  3. potrash
    October 9, 2013 at 3:23 am

    Great code 🙂

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: