this is a recursive problem, the moment it says that there are n lists, it
becomes recursive, the solution i have given can be made generic even though
the sample is for 3
if total number of elements in a list is m i.e. 2 power k
//function to merge two lists
L1S//represents start of list 1
L2S//represents start of list 2
L1E//end of list 1(may not be needed)
L2E//endof List
L1C//number of elements treated as single element in list 1
L2C//number of elements treated as single element in list 2
for (int pass=1; pass<=k;pass++)
{
passS1= L1E-pass*L1C;
passS2=L2S;
for (int swapCount=1;swapCount<=pass;swapCount++)
{
swap(a[passS1], L1C, a[passS2],L2C);
passS1 +=L1C; passS2 +=L2C;
}
}
this is generic for two lists
//function to merge n lists
for (int merge=1; merge<=n;merge++)
{
bstart=m*merge;
bend= bstart+m;
b=&a[bstart];
mergeTwo(a, astart, aend, aele,b, bstart, bend, bele);
aele++;
}
this can be improved to merge two lists in parallel
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Thu, Jul 22, 2010 at 10:37 PM, Tech Id <tech.login....@gmail.com> wrote:
>
> In the final position, element at
> arr[0] remains at arr[0]
> arr[1] comes at arr[3]
> arr[2] comes at arr[6]
> arr[n] comes at arr[3n-3] position
> So element at k goes at 3k, if 1 <= k < n
>
> arr[n] comes at arr[1]
> arr[n+1] comes at arr[4]
> arr[n+2] comes ar arr[7]
> arr[2n-1] comes ar arr[3n-2]
> So element at k goes at (k-n)*3+1, if n <= k < 2n
>
> arr[2n] comes at arr[2]
> arr[2n+1] comes at arr[5]
> arr[2n+2] comes at arr[8]
> arr[3n-1] remains at arr[3n-1]
> So element at k goes at (k-2n)*3+2, if 2n <= k < 3n-1
>
> So, we can have a function req_pos which will return the required
> position for a number if its current position is given.
> int req_pos (int k, int n) {
> if (k < n) {
> return 3*k;
> }
> if (k < 2n) {
> return (k-n)*3+1;
> }
> return (k-2n)*3+2;
> }
>
> int k=1;
> for (int i=0; i<3n-1;i++) {
> int new_k = req_pos (k);
> swap (arr, k , new_k);
> k = new_k;
> }
>
> The above loop runs 3n times, which is sufficient to cover all the
> numbers.
> Only problem is that if k becomes equal to any previous value already
> covered, then it will fall into a loop and swap already swapped
> integers.
> If someone can prove that this will not happen, then we have an O(n)
> in-place solution.
>
> For n=10, k will have values like:
> 1, 3, 9, 27, 23, 11, 4, 12, 7, 21, 5, 15,
>
> Yoo-hoo... seems like it works!
> Please comment.
>
>
>
> On Jul 22, 7:02 pm, Ashish Goel <ashg...@gmail.com> wrote:
> > 123456789
> > then interchange middle one of 123 and 456
> > 12 43 56 789
> > now exchange in pairs except first and last i.e. 24 ->42, 35->53
> > 1 42 53 6 789
> > now treat 14 as single number, 25 as single number ans 36 as single
> number
> > and again apply this logic
> > 14257 36 89
> > 14 725 836 9
> >
> > need time to program this, a bit busy...
> >
> > done :)
> >
> > Best Regards
> > Ashish Goel
> > "Think positive and find fuel in failure"
> > +919985813081
> > +919966006652
> >
> > On Thu, Jul 22, 2010 at 5:58 PM, UMESH KUMAR <kumar.umesh...@gmail.com
> >wrote:
> >
> >
> >
> > > Qn:-in the given array elements
> > > a1a2a3a4......anb1b2b3b4.......bnc1c2c3c4........cn
> > > without take a extra memory how to merge just like?
> >
> > > a1b1c1a2b2c2a3b3c3............................anbncn
> >
> > > --
> > > 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>
> <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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
