Algorithm For Sequence Prb

Algorithm for sequence prb we have an array of 2n elements like "a1 a2...an b1 b2...bn". WAP to rearrange the array as "a1 b1 a2 b2...an bn" time complexity is O(n) no extra array or memory can be taken...

•

•

•

• •

Initialize a variable with count = (length of array – 2). This is the number of total transformations that we have to do, in order to get the desired array. Minus 2 because the first and the last element remain at their place, while the rest of the elements are moved. Since second element is bound to be moved, then we’ll start with the second element in the array. We calculate the position of second element. It gets moved to third position. So we move it to third position. The third position moves to fifth position and so on and so forth. We go on replacing the elements till we arrive at the second place (that’s right it forms a loop). Every time we replace a value we decease the count by one. If after the loop, count !=0, that means we still have some elements that have not been swapped. The next element from where to start the loop would be the fourth element. If after this loop still some elements are left, then we start at 6th position, then 8th, then 10th until count > 0. When count == 0, then we’ll have the desired array. Make a few diagrams, you’ll understand the pattern.

Illustration 1

0

1

2

3

4

5

6

0

1

2

3

4

5

6

Illustration 2 Loop2

Loop1

0

1

2

3

4

0

1

2

3

4