Arunachalam wrote: > Hi, > can you please elaborate on your question? > > If I understand you correct then you are given an array of Length 2n with > elements a1,a2...an,b1,b2.. bn. > > Now you are asked to modify the array to a1,b1,a2,b2.....an,bn. > > If this is the problem then the solution is straight forward. For each > element not in place try to find its destination. Make a backup of the > destination and then put this element there and mark the current location as > empty. Now Keep on doing this until the destination reaches an empty place. > When destination reaches empty place restart the process. > > This is of O(n) Since at the first time itself the element will be moved to > its place. And for the element in its place we will not do any processing. > So this is clearly of order n.
This "cycle leader" algorithm requires some care to ensure an O(n) running time. The trick is to know the first element in each of the cycles - otherwise you won't know which elements have already moved. This can be done, but it's nontrivial. Try googling for "perfect shuffle" and "cycle leader". --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
