starting from an .. do shifts to place an, an-1 ... on their correct destinations
but when you come to pick displaced bn's (into a's half) back. you got to keep track of
2 positions at a's half.
this way you will finally get to the solution in o(n) time and o(1) space.
On 7/7/06, Ranjit <[EMAIL PROTECTED]> wrote:
Yet another approach. If instance size is n,
A B C D a b c d
1. swap the element at n/2 and n-1
A B C c a b D d
2. shift "a" and "b"
A B a b C c D d
Now the instance size is n/2 (A B a b) Recursively perform steps 1. and
2. on it.
The swaps are constant only the shifts are a function of n.
--
Munish Goyal
Denali Software Inc.
Bangalore
919342539813
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
