if the array is numbered from 0..(2n-1)
i= initial position of int/char
f= final position of int/char
if (i (2n-1)/2) #for integer
f = i+i
else #for char
f = i - ((2n-1)-i)
so iterate through the array in the following way
choose first element
determine it final position
put the element in
Observation:
Following is the sequence of indices which we want to swap:
(2,n+1)
(3,n+1)
(4,n+2)
(5,n+1)
(6,n+3)
(7,n+2)
(8,n+4)
(9,n+3)
Hence, for even indices we swap (k,n + k/2) and for odd indices, we swap(k,
n + k/2-1).
This is O(n). and constant space.
for(k=1;k=2*n;k++) {
if(k%2==0) {
@Nikhil Jindal
check your fromula for indices when k = 3
it is k/2 - 1 = 0
thus it will give swap(3,n).
On Sat, Aug 7, 2010 at 5:37 PM, Nikhil Jindal fundoon...@yahoo.co.inwrote:
Observation:
Following is the sequence of indices which we want to swap:
(2,n+1)
(3,n+1)
(4,n+2)
Here's a solution that I am pretty sure is less than O(n^2). The data
are moved only once, but timing the routine suggests that it is O(n
log n), but I have no proof of that.
The first and last do-while loops move cycles of data, while the
nested do-while loops find the beginning index of a new
