http://anandtechblog.blogspot.com/2011/06/in-place-shuffle.html
On Mon, Jan 10, 2011 at 9:06 AM, anurag.singh <anurag.x.si...@gmail.com>wrote: > 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: [assuming all elements are > 0) > > Negate all elements (a[i] = -1 * a[i];) > 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] = -1 * A[current_index]; > if current_element > 0 then > to_index = index of next negative element. > current_index = to_index; > while A[current_index] < 0 > > Algo can be modified to check in other cases like when elements can be > negative also, OR elements are characters, strings. > There can be different ways to track if all elements are processed or > not, depending on problem. > e.g. if negative elements are also in input then, > Add some very very negative no to all elements say -50000 and while > assigning it to to_index, adding 50000 > If element are characters, string then attach some keyword (prefix or > suffix) to each element, > while assigning it to to_index, remove the attachment. > > 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 algogeeks@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. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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.
