OK. I hope following should do the needful.
Input:
a1,a2,a3,a4,.....aN,b1,b2,b3,b4,.....,bN
Output:
a1,b1,a2,b2,a3,b3,a4,b4,..........aN,bN.
If we notice, there is a pattern for all elements while shuffling.
For all elements from 1st half portion (a1 to aN)
a[i] is moved to a[2*i] where 0<= i <= N [say array name is a]
i.e.
a[0] is moved to a[0] (for i=0, i = 2*i =0)
a[1] is moved to a[2]
a[2] is moved to a[4]
a[3] is moved to a[6]
......
....
For 2nd half, same is true from opposite (OR if we see array
inverted,b1 to bN behaves same as a's)
In other words, keeping array as is, 2nd half of the array (b1 to bN)
goes like this
a[i] is moved to a[n-2*(n-i)] where N < i < 2N
i.e. (Assuming 2nd half array starting with index i=7, so total array
size 12)
a[7] moved to a[1]
a[8] moved to a[3]
a[9] moved to a[5]
overall as example:
Input
a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8], a[9], a[10],
a[11]
Output:
a[0], a[6], a[1], a[7], a[2], a[8], a[3], a[9], a[4], a[10], a[5],
a[11]
And I believe it's pretty straightforward to implement this. using
only few extra variables [not dependent on array size](Based on
implimentation).
So, O(n) time and O(1) space.
Alg:
current_index = 0;
current_element=A[0];
do
if current_index <= n/2 then
to_index = 2*current_index
else
to_index = (size -1) - 2*(size - 1 - current_index)
end if
current_element = A[to_index];
A[to_index] = A[current_index];
current_index = to_index;
while all elements are not done
Please advise if you find any issue with this.
On Jan 10, 5:51 pm, juver++ <avpostni...@gmail.com> wrote:
> There is only one single array.
--
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.
