Actually the solution is best thought of with recursion.
See, for a simple 4 element array: a1 a2 b1 b2, you can get the result
by swapping only the two elements in the middle.
Now think, if you had an 8 element array: a1 a2 a3 a4 b1 b2 b3 b4,
group these into pairs of 2 like: a1 a2 - b1 b2 / a3 a4 - b3 b4
(logical grouping with pos0, pos1 with poslen/2, poslen/2 + 1)
Perform swap as before, you get: a1 b1 a2 b2 a3 b3 a4 b4, of course in
the array it will actually be: a1 b1 a3 b3 a2 b2 a4 b4 (since the
grouping was logical)
Perform same swap, but this time consider pairs as [a1 b1] [a3 b3] /
[a2 b2] [a4 b4]. Think of elements in brackets as one element. Same
swap operation yields
a1 b1 a2 b2 a3 b3 a4 b4.
For larger numbers a1 a2 a3 a4 a5 a6 a7 a8 b1 b2 b3 b4 b5 b6 b7 b8
Step 1: Group as: [a1 a2 a3 a4] [a5 a6 a7 a8] [b1 b2 b3 b4] [b5 b6 b7
b8]
Step 2: swap the two elements in the middle: [a1 a2 a3 a4] [b1 b2 b3
b4] [a5 a6 a7 a8] [b5 b6 b7 b8]
Step3: Group as: group 1 [a1 a2] [a3 a4] [b1 b2] [b3 b4] group 2: [a5
a6] [a7 a8] [b5 b6] [b7 b8]
Step 4: swap: [a1 a2] [b1 b2] [a3 a4] [b3 b4] [a5 a6]
[b5 b6] [a7 a8] [b7 b8]
Step 5: Group as: group1: a1 a2 b1 b2 group2: a3 a4 b3 b4 group3 a5 a6
b5 b6 group4 a7 a8 b7 b8
Step6: swap as above: a1 b1 a2 b2 a3 b3 a4 b4 a5 b5 a6 b6 a7 b7 a8 b8
Since grouping is logical, it has taken only 3 steps to solve a
problem with 16 elements. Total number of steps required for this
solution is
{ln to base 2 (length/2)}. So, for 16 elements, 16/2 = 8, 2^3 = 8. For
64 elements, 64/2 = 32; 2^5 = 32. so 5 steps will be required.
Although, total number of swaps will be larger = (length/4) * number
of steps = 4 * 3 = 12 for a1...a8b1...b8.
Which is still less than O(n) = 16 :-)
-Minotauraus.
On Jun 7, 9:03 pm, Rohit Saraf <rohit.kumar.sa...@gmail.com> wrote:
> Of course you should do it via swappings.. why would one think of anything
> else :)
> --------------------------------------------------
> Rohit Saraf
> Second Year Undergraduate,
> Dept. of Computer Science and Engineering
> IIT Bombayhttp://www.cse.iitb.ac.in/~rohitfeb14
>
> On Mon, Jun 7, 2010 at 10:39 PM, vadivel selvaraj
> <gct.vadi...@gmail.com>wrote:
>
>
>
> > Hi guys d soln z quite easy by swapping the variables..
> > consider a1a2a3a4b1b2b3b4
> > In the first iteration, swap (a2,b1),(a4,b3) giving a1b1a3b3a2b2a4b4
> > In the second iteration, swap (a3b3,a2b2) which gives d soln...
> > a1b1a2b2a3b3a4b4...
>
> > Any comments on dis??
>
> > On Mon, Jun 7, 2010 at 1:51 PM, Raj N <rajn...@gmail.com> wrote:
>
> >> @sain: But the question demands O(n) time
>
> >> On Mon, Jun 7, 2010 at 3:35 AM, Anand <anandut2...@gmail.com> wrote:
>
> >>> Here is my approach is o(n).
> >>>http://codepad.org/YAFfZpxO
>
> >>> <http://codepad.org/YAFfZpxO>
>
> >>> On Sun, Jun 6, 2010 at 7:28 AM, sharad kumar
> >>> <sharad20073...@gmail.com>wrote:
>
> >>>> this is ques by adobe and they want inplace soln......
>
> >>>> --
> >>>> You received this message because you are subscribed to the Google
> >>>> Groups "Algorithm Geeks" group.
> >>>> To post to this group, send email to algoge...@googlegroups.com.
> >>>> To unsubscribe from this group, send email to
> >>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups
> >>>> .com>
> >>>> .
> >>>> For more options, visit this group at
> >>>>http://groups.google.com/group/algogeeks?hl=en.
>
> >>> --
> >>> You received this message because you are subscribed to the Google Groups
> >>> "Algorithm Geeks" group.
> >>> To post to this group, send email to algoge...@googlegroups.com.
> >>> To unsubscribe from this group, send email to
> >>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups
> >>> .com>
> >>> .
> >>> For more options, visit this group at
> >>>http://groups.google.com/group/algogeeks?hl=en.
>
> >> --
> >> You received this message because you are subscribed to the Google Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to algoge...@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups
> >> .com>
> >> .
> >> For more options, visit this group at
> >>http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > Simplicity is prerequisite for reliability.
> > – Edsger W. Dijkstra
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algoge...@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups
> > .com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
