Archive

Archive for the ‘algorithm’ Category

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

October 30, 2011 3 comments

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

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

October 30, 2011 1 comment

Give an efficient 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)

Categories: algorithm

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.

Categories: algorithm