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
- Examine(A,i) — report the color of the ith element of A.
- 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.
