In order to make it "inplace", time complexity has gone to n^2.
Rearrange(array,int N) //So array size is 2N
{
int i = 1;//points to index array[1] which has a2 since a1 is already
at the correct place;
int j = N;//array[0] to array[N-1] is a1 to aN. so j is index of b1
//it is assumed that N is
for(;j < 2N;j++)
{
int bValue = array[j];
//right shift all elements from j to i (moving right to left)
for(int k = j; k>i ; k--)
{
array[k]=array[k-1];
}
//k now is equal to i but a2 has shifted to array[2] from
array[1];
array[k] = bValue;
i = i+2;//No need to consider array[i+1] as that element (a2 in
first iteration is at its proper place
}
}
Space Complexity: Inplace
Time Complexity:
to move b1 : a2 to aN i.e., N-1 right shifts
to move b2 : a3 to aN i.e., N-2 right shifts
...
to move b(N-1): aN moved right: 1 right shift
so total shifts=1+2+3+.....N-1
hence time complexity = n^2
Let me know if you have comments or improvements.
Sain
On Jun 6, 7:28 pm, sharad kumar <[email protected]> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
