## 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.

## [3] Give an eﬃcient algorithm to rearrange an array of n keys so that all the negative keys precede all the nonnegative keys.

Give an eﬃcient algorithm to rearrange an array of n keys so that all the

negative keys precede all the nonnegative keys.

Solution:

1. Scan through the list from left to right through i .

2. Point the first positive number in the list say it j (initially -1).

3. When List[i] is a negative number and j >-1, swap list[i] & list [j] and increment j by 1

4. When List[i] is a negative number and j == -1, we haven’t get any positive number and go through scanning.

Complexity : O(n)

## Difference between coin change and 01 knapsack problem….

In Coin change Problem you can take any coin more than once. But in 01 knapsack you can take one item only once. This is why the solution for 01 knapsack and coin change differs.