CareerCup

Algorithm:

First swap elements in the middle pair
Next swap elements in the middle two pairs
Next swap elements in the middle three pairs
iterate n-1 steps.

Ex: with n = 4.
a1 a2 a3 a4 b1 b2 b3 b4
a1 a2 a3 b1 a4 b2 b3 b4
a1 a2 b1 a3 b2 a4 b3 b4
a1 b1 a2 b2 a3 b3 a4 b4

Anony and Adiser
I think there is an O(n) sol for this :)
I went thro some examples and the new position of an elt can be given mathematically
new id=(2*old id)%N...here N is the final index...not the number of elts...or (no of elts-1)
Heres the code

Re-arrange(int[] a){
   int count=0;int i=1,int temp=a[1];
   while(count<(N-1)){//to keep track of no:re-arranges which is N-1 in total
      swap(temp,a[(2*i)%N]);
      i=(2*i)%N;
      count++;
   }
}

I believe Anon has done the same above

Copies from another similar question asked in this forum

Algorithm:

First swap elements in the middle pair
Next swap elements in the middle two pairs
Next swap elements in the middle three pairs
iterate n-1 steps.

Ex: with n = 4.
a1 a2 a3 a4 b1 b2 b3 b4
a1 a2 a3 b1 a4 b2 b3 b4
a1 a2 b1 a3 b2 a4 b3 b4
a1 b1 a2 b2 a3 b3 a4 b4

This is in place array transpose.

#include <stdio.h>
 
int get_index(int idx, int N) {
    return (idx % 2) * N + (idx / 2);
}
 
void swap(int *a,int *b)
{
        int t=*a;
        *a=*b;
        *b=t;
}
 
void transform_array2(int *s, int len) {
    int N = len / 2,i;
    for(i = 0; i < len; i++) {
        int new_idx = get_index(i, N);
        while(new_idx < i) {
            new_idx = get_index(new_idx, N);
        }
        printf("i: %d; new_idx: %d\n", i, new_idx);
        swap(&s[i], &s[new_idx]);
    }
    for(i = 0; i < len; i++) {
        printf("%d ", s[i]);
    }
    printf("\n");
}
 
int main()
{
        int arr[]={1,2,3,4,5,6,7,8,9,10,11,12};
        transform_array2(arr,12);
        return 0;
}

Time complexity-O(n)

Use divide and conquer for n log n. This is faster than O(n) in-place transposes on real hardware because of caching effects. (Yes, I've tried it.)

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+1)-2*(n-i)] where n/2 < 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
implementation).
So, O(n) time and O(1) space [IN PLACE].

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 - 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.

public static void reorder(char[] input, int n) {
		for (int i = 1; i < input.length; i = i+2) {
			int replaceElem = (2*n + i - 1)/ 2;
			char swap = input[replaceElem];
			for (int j = replaceElem; j > i; j--) {
				input[j] = input[j-1];
			}
			input[i] = swap;
		}
	}

@blueskin: Yes, my algorithm has O(n*n) time complexity but O(1) space complexity. Your algorithm will need additional storage to store the corresponding values.

If we are allowed O(n) space complexity, the simplest thing to do would be to just use two queues. Put values a1 to an in Q1 and b1 to bn in Q2. Now, just dequeue one element from each and keep populating the array. O(n) time.

public static void ReOrder(ArrayList a)
{
for(int i=a.size()/2; i<a.size(); i++){
int finalPos=((i-a.size()/2)+1)*2-1;
String temp=a.get(i).toString();
for(int j=i; j>finalPos; j--){
a.set(j, a.get(j-1));
}
a.set(finalPos, temp);
}
}

If [a1,a2,a3...,an,b1,b2...bn] is given input change this to [a1,b1,a2,b2.....an,bn]

The idea is to move index 2 everytime, starting at 1.
swap a[i] with a[len/2+i] - a1,b1,a3,a2,b2,b3.
swap a[i+1] with a[len/2+i] - a1,b1,a2,a3,b2,b3.

The idea to start with keep every 2 things in order and move forward.

lets take a0, a1, a2, a3, a4, b0, b1, b2, b3 ,b4, b5.
1) swap a1 with b0 to get

a0, b0, a2, a3, a4, a1, b1, b2, b3 ,b4.

2) shift a1 to arr[2] to get
a0, b0, a1, a2, a3, a4, b1, b2, b3 b4.

now we reduced problem from 10no.arry to 8no. array.
two steps take n/2 swaps. decreasing by 1 with each iteration. so order is O(n2).

otherthan this, i did nt see a better solution. Can any one improve this?

I tried a recursive process of starting at pos1, moving it to its correct place, then moving the element there to its correct place in tunr, once you have done len -1 steps you are done. You wont get any cycles because you are always putting something in its correct place - no 2 elements can be in the same place. Only the first element starts off in its correct place. Not sure if stack for recursion violates in-place though

def switch(arr, ind, mid, curr_val, step):
    if ind < mid:
        new_ind = ind*2
    else:
        new_ind = (ind - mid) * 2 + 1
    next_val = arr[new_ind]
    arr[new_ind] = curr_val
    print "ind: %s, new_ind: %s, next_val: %s, curr_val: %s"
    print '%s' % arr
    if step < mid*2-1:
        switch(arr, new_ind, mid, next_val, step+1)

def gen_arr(size):
    arr = []
    for i in range(size):
        arr.append('a%s'%(i+1))
    for i in range(size):
        arr.append('b%s'%(i+1))
    return arr

size = 15
print gen_arr(size)
switch(gen_arr(size), 1, size, 'a2', 1)

Anurag,

how many times does the nested for loop run for each iteration? does nt that change order?

yup that works :) cool soln. thx satya.

Another O(n) solution based on divide-and-conquer. Recursively divides n by 2, and use the result of two halves to merge the final result.

Examples demonstrate for n = 2^k. When n is not 2^k, we can add some dummy elements, and do the same process, and finally discard those that are dummy.

n = 1: a1 b1
n = 2: 
a1 a2 b1 b2 => a1 b1 a2 b2
n = 4:
a1 a2 a3 a4 b1 b2 b3 b4 =>  a1 a2 b1 b2 a3 a4 b3 b4 
			=>  a1 b1 a2 b2 a3 b3 a4 b4 
n = 8:
   a1 a2 a3 a4 a5 a6 a7 a8 b1 b2 b3 b4 b5 b6 b7 b8 
=> a1 a2 a3 a4 b1 b2 b3 b4 a5 a6 a7 a8 b5 b6 b7 b8 
=> a1 b1 a2 b2 a3 b3 a4 b4 a5 b5 a6 b6 a7 b7 a8 b8

1st step takes n/2 swap, 2nd step n/4 swaps. Total steps O(log n). So, total complexity O(n).

I took anon's code for making the list but a different approach for arranging it - I believe this is O(n) and satisfies the in-space problem

def gen_arr(size):
    arr = []
    for i in range(size):
        arr.append('a%s'%(i+1))
    for i in range(size):
        arr.append('b%s'%(i+1))
    return arr
size = 15
arr = gen_arr(size)
index = size
while index < len(arr):
    arr.insert(((index-size)*2)+1,arr[index])
    index += 1
    del arr[index]
print arr

The approach iterates over the last half of the list taking each element and inserting it in its correct place then removing the next element (since the front part of the list has grown by 1)

O(N) ...

#include <iostream>
#include <vector>
#include <string>
#include <stdio.h>

using namespace std;

vector<string>::iterator iter;

void swap (string& s1, string& s2) {
    string s = s1;
    s1 = s2;
    s2 = s;
}

void print (vector<string>& str_arr) {
    for (iter = str_arr.begin (); iter != str_arr.end (); ++iter) {
        cout << *iter << " ";
    }
    cout << endl;
}

void reorder(vector<string>& str_arr) {
    int n = (str_arr.size () >> 1);
    int t;
    string s;
    for (int i = 1; i < n; i += 2) {
        t = i;
        s = str_arr[t];
        str_arr[t] = "$$";
        do {
            if (t < n) {
                t = (t << 1);
            } else {
                t = ((t - n) << 1) + 1;
            }
            swap (s, str_arr[t]);
        } while (s.compare("$$") != 0);
    }
}

int main () {
    int n;
    cin >> n;
    char c_str[3];
    string* str;
    vector<string>* str_arr = new vector<string>();
    for (char c = 'a'; c < 'c'; ++c) {
        for (int i = 0; i < n; ++i) {
            sprintf (c_str, "%c%d", c, i);
            str = new string (c_str);
            str_arr->push_back (*str);
        }
    }
    print (*str_arr);
    reorder (*str_arr);
    print (*str_arr);
    return 0;
}

#include <stdio.h>

struct demo{
  char c[3];
};

void swap(struct demo *a, struct demo *b)
{
  struct demo temp;
  temp = *a;
  *a = *b;
  *b = temp;
}

int  main()
{
  int size,i,j,p,x,y;
  static struct demo ab[10] = {{"a1"},{"a2"},{"a3"},{"a4"},{"a5"},{"b1"},{"b2"},{"b3"},{"b4"},{"b5"}};

  size = sizeof(ab)/sizeof(ab[1]);

  for(i=0;i<size;i++)
  {
    printf("%s ",ab[i].c);
  }
  printf(" \n");
  p=size/2;

  for(i=0; i<(size/2)-1; i++)
  {
    for (j=0;j<=i;j++)
    {
      x = (p-1-i) + (2*j);
      y = (p-i) + (2*j);
      //printf("Index is %d %d \t",x,y);
      swap(ab+x,ab+y);
    }
  }
  printf("\n");
  for(i=0;i<size;i++)
  {
    printf("%s ",ab[i].c);
  }
  return 0;
}

// extension of swapping problem

j=n;
for(i=1;i<n;i++)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
j++;
}

// extension of swapping problem

j=n;
for(i=1;i<n;i++)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
j++;
}

// extension of swapping problem

j=n;
for(i=1;i<n;i++)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
j++;
}

@ankur

Please run through the code.I don't think it is correct.
REsulting order has to be
a1,b1,a2,b2,a3,b3 ....

Though bad in terms of efficiency, it can be done in way of insertion sort, where pick b1 and insert at 2nd position and copy a2-an one by one till b1 position

void printArray(char a[][5],int len) {
int i;
for(i=0;i<len;i++) {
printf("%s ",a[i]);
}
printf("\n");
}

void shuttleArray(char a[][5],int len) {
printArray(a,len);
int count=1; int i,j; int pos=0;
char *newbuf=(char *)malloc(5);
char *oldbuf=(char *)malloc(5); char *tmp;
int *mark=(int *)malloc(sizeof(int)*len);
for(i=0;i<len;i++)
mark[i]=0;
i=1;
strcpy(oldbuf,a[i]);
mark[0]=1;
while(count<len) {
if(i<len/2)
pos=(2*i+1)%len-1;
else
pos=(2*i)%len+1;
strcpy(newbuf,a[pos]);
strcpy(a[pos],oldbuf);
mark[i]=1;
tmp=oldbuf;
oldbuf=newbuf;
newbuf=tmp;
i=pos;
if(mark[i]==1) {
for(j=0;j<len;j++)
if(mark[j]==0)
break;
i=j;
strcpy(oldbuf,a[i]);
}
++count;
}
printArray(a,len);
}

int main(void) {
//puts("!!!Hello World!!!"); /* prints !!!Hello World!!! */
//int a[]={1,2,3,3};
//permutation(a,4,0);
char a[10][5];//={"a0","a1","a2","a3","a4","b0","b1","b2","b3","b4"};
int i,pos;
for(i=0;i<5;i++) {
sprintf(a[i],"a%d",i);
}
for(i=0;i<5;i++) {
sprintf(a[i+5],"b%d",i);
}
int len=10;
for(i=0;i<len;i++) {
if(i<len/2)
pos=(2*i+1)%len-1;
else
pos=(2*i)%len+1;
printf("%d ",pos);
}
printf("\n");
shuttleArray(a,10);
return EXIT_SUCCESS;
}

for(i=1,j=n ; j<2n||i<2n; i+=2,j++)
{
temp = arr[j];
for(k=j;k>=i;k--)
arr[k]=arr[k-1];
arr[i] = temp;
}

void printArray(char a[][5],int len) {
int i;
for(i=0;i<len;i++) {
printf("%s ",a[i]);
}
printf("\n");
}

void shuttleArray(char a[][5],int len) {
printArray(a,len);
int count=1; int i; int pos=0;
char *newbuf=(char *)malloc(5);
char *oldbuf=(char *)malloc(5); char *tmp;
i=len/2;
strcpy(oldbuf,a[i]);
while(count<len) {
if(i<len/2)
pos=(2*i+1)%len-1;
else
pos=(2*i)%len+1;
strcpy(newbuf,a[pos]);
strcpy(a[pos],oldbuf);
tmp=oldbuf;
oldbuf=newbuf;
newbuf=tmp;
i=pos;
++count;
}
printArray(a,len);
}

void cyclicswap(int *arr1, int *arr2)
{
int n = arr2-arr1;
int temp = *arr2;
while(arr2!=arr1)
{
*arr2 = *(arr2-1);
arr2--;
}
*arr1 = temp;;
}

void rearrange(int *arr,int n)
{
if (n==2)
return;
swap(arr+1, arr+(n/2));
cyclicswap(arr+2,arr+(n/2));
rearrange(arr+2,n-2);
}

main()
{

rearrange(arr,sizeof(arr)/sizeof(arr[0]));
}

the index i is from 1 to 2n.
if i <= n,
j=2*i-1, //the final place
else
j=2*(i-n)

use a loop from 2 to n-1 to put each element into the final place.

void rearrange(int *a, int n)
{
for(int i = 1; i < 2*n; ++i)
{

}
}

+23 int chars_left = n/2;
+24 for(int position = 1; chars_left != 1; chars_left--,position = position+2)
+25 {
+26 for(int i = n - chars_left; i > position; i--)
+27 {
+28 int temp = c[i];
+29 c[i] = c[i-1];
+30 c[i-1] = temp;
+31 }
+32 }

If N is power of 2, swap the second half of a[i] with the first half of b[i] with O(N/2) operations.
Then recursively do rearrange of the first N elements and the second N elements.
If N is not power of 2, some spacial handling is needed to decide how many elements to swap each time. But it does not change the complexity.
The overall complexity is O(NlgN).

Ch.v.Suresh:

Under line high lighted are shift elements.

One shift:

a1 a2 a3 a4 a5 a6 a7 a8 ---> Even postions
-- -- -- --
b1 b2 b3 b4 b5 b6 b7 b8 ---> Odd positions
-- -- -- --

Two shift:


a1 b1 a3 b3 a5 b5 a7 b7
----- -----
a2 b2 a4 b4 a6 b6 a8 b8
----- -----

Four shift:


a1 b1 a2 b2 a5 b5 a6 b6
-----------
a3 b3 a4 b4 a7 b7 a8 b8
-----------

Result:

a1 b1 a2 b2 a3 b3 a4 b4 a5 b5 a6 b6 a7 b7 a8 b8

Ch.v.Suresh:

Under line high lighted are shift elements.

One shift:

a1 a2 a3 a4 a5 a6 a7 a8 ---> Even positions a2,a4,a6,a8
-- -- -- --
b1 b2 b3 b4 b5 b6 b7 b8 ---> Odd positions b1,b3,b5,b7
-- -- -- --

Two shift:

a1 b1 a3 b3 a5 b5 a7 b7 --> Even positions (a3,b3) , (a7,b7)
----- ----- --> Odd positions (a2,b2) , (a6,b6)
a2 b2 a4 b4 a6 b6 a8 b8
----- -----

Four shift:

a1 b1 a2 b2 a5 b5 a6 b6 --> Shift (a5,b5,a6,b6) with (a3,b3,a4,b4)
-----------
a3 b3 a4 b4 a7 b7 a8 b8
-----------

Result:

a1 b1 a2 b2 a3 b3 a4 b4 a5 b5 a6 b6 a7 b7 a8 b8

#include<stdio.h>
#include<conio.h>
/*a1b1a2b2a3b3*/
void set(char a[],int m1,int m2);
int main()
{
char a[7]={'a','c','e','b','d','f','\0'};
int m1,m2,len,i;
len=strlen(a);
m1=(len-1)/2;
m2=m1+1;
set(a,m1,m2);
for(i=0;i<len;i++){
printf("%c",a[i]);}
getchar();
getchar();
return 0;
}
void set(char a[],int m1,int m2)
{
int len;
char t;
len=strlen(a);
t=a[m1];
a[m1]=a[m2];
a[m2]=t;
while(m1>1 && (m2<(len-1)))
{
t=a[m1];
a[m1]=a[m1-1];
a[m1-1]=t;
t=a[m2];
a[m2]=a[m2+1];
a[m2+1]=t;
--m1;++m2;
}}

#include<stdio.h>
#include<conio.h>
/*a1b1a2b2a3b3*/
void set(char a[],int m1,int m2);
int main()
{
char a[7]={'a','c','e','b','d','f','\0'};
int m1,m2,len,i;
len=strlen(a);
m1=(len-1)/2;
m2=m1+1;
set(a,m1,m2);
for(i=0;i<len;i++){
printf("%c",a[i]);}
getchar();
getchar();
return 0;
}
void set(char a[],int m1,int m2)
{
int len;
char t;
len=strlen(a);
t=a[m1];
a[m1]=a[m2];
a[m2]=t;
while(m1>1 && (m2<(len-1)))
{
t=a[m1];
a[m1]=a[m1-1];
a[m1-1]=t;
t=a[m2];
a[m2]=a[m2+1];
a[m2+1]=t;
--m1;++m2;
}}

input: "0123456789"
output: "0516273849"

char str[] = "0123456789"
CALL:
	EvenMix(str,0,strlen(str)-1,strlen(str))
	
	
void EvenMix(char *str, int start, int end, int len)
{
	if(len <= 2) return;
	else{
		swap(str,start,end,len);
		EvenMix(str, start, ((len>>2)-1), len>>2);
		EvenMix(str, start, len>>2, len-1, len>>2);
	
	}
	
}

void swap(char *str, int start, int end, int len)
{
	int x = len>>2
	int p = (start + x)>>2;
	int q = (x + end)>>2;
	
	while(x <= q)
	{
		char temp = *(str + start + p);
		*(str + start + p) = *(str + start + x);
		*(str + start + x); = temp
	}
}

void ArrangeIntegers(int[] numbers)
{
if (numbers != null && numbers.Length > 3)
{
int n = numbers.Length;
int ps = 1;
int pe = (n / 2) - 1;
int qs = (n / 2);
int qe = n - 2;
Queue<int> numque = new Queue<int>();
numque.Enqueue(numbers[ps]);
numque.Enqueue(numbers[qe]);
bool fAlt = true;

while (ps < qe)
{
if (fAlt == true)
{
int t1 = numbers[ps];
numbers[ps] = numbers[qs];
numbers[qe] = (ps == pe)? t1 : numbers[pe];
fAlt = false;
pe--;
qs++;
}
else
{
numque.Enqueue(numbers[ps]);
numque.Enqueue(numbers[qe]);
numbers[ps] = numque.Dequeue();
numbers[qe] = numque.Dequeue();
fAlt = true;
}
ps++;
qe--;
}
}
}

ArrangeIntegers function can also written as generic function to handle the different type of data types. This is function has O(log n) time complexity.

One additional check I missed was to check (numbers.Length % 2 == 0) just to make sure 2n condition holds.

I have a O(n) method with O(1) space.
Since every element is not in its final position except first and last element, we can randomly pick one element at first, for example the second one(a2), record its posision(currentIndex) and do the following loop until a2 in its final position(currentIndex==2):
1. calculate which element should be in this currentIndex position
if currentIndex is even number, the element should be in this position is a1...an. We use currentIndex/2 to calculate the current position of this element(index)
if currentIndex is odd numver, the element should be in this position is b1...bn. we use (currentIndex-1)/2+n
2. swap arr[currentIndex] and arr[index].
3. record the current position of a2(currentIndex).

void DoChangeElement(int currentIndex, int * arr, int length)
{
	if (length&1)
	{
		cout<<"Length must be even and big than 0."<<endl;
		return;
	}
	if(length==1) return;
	//loop until a2 is in its right position
	while(currentIndex!=2)
	{
		//calculate the right element for this currentIndex
		int index=0;
		if(currentIndex&1) index=(currentIndex-1)/2+(length/2);
		else index=currentIndex/2;

		swap(arr[currentIndex],arr[index]);
		currentIndex=index;
	}

}

//arr = {a1,a2,a3,...,an,b1,b2,b3...,bn}
//array index starts from 0 and goes to arr.length - 1

public static void main(String[] args) {
int i;
int [] arr = {11,12,13,14,15,16,17,1,2,3,4,5,6,7};
//int [] arr = {1,2,3,4,5,6,7,11,12,13,14,15,16,17};
boolean isOdd = (((arr.length /2) % 2) != 0)? true:false;

printArr(arr);
//First Loop
for (i = 1; i < (arr.length /2); i+=2) {
swap(arr,i,(arr.length /2) + i - 1);
}
printArr(arr);
//Second Loop
if(isOdd){
for (i = (arr.length/2)-1; i < arr.length-2; i++) {
swap(arr,i,i+1);
}
}
printArr(arr);
final int N = isOdd? (arr.length-2)/2:arr.length/2;
int itr = N;
int x=0;
for (i = 2; i <2*N && itr < 2*N; i+=2)
{
if(arr[i]> arr[itr])
{
if(i<itr) {
swap(arr,i,itr);
swap(arr,i+1, itr+1);
x++;
if(x==2)
{
itr+=2;
x=0;
}
}
}
else{
if(i>itr) {
swap(arr,i,itr);
swap(arr,i+1, itr+1);
}
}
}
printArr(arr);
}

static void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
static void printArr(int []arr){
for(int i = 0; i < (arr.length);i++){
System.out.print(arr[i]);
if (i!=arr.length-1)
System.out.print(",");
}
System.out.println();
}

//----------------REFORMATTED ABOVE-----------------------
//arr = {a1,a2,a3,...,an,b1,b2,b3...,bn}
//array index starts from 0 and goes to arr.length - 1



public static void main(String[] args) {
int i;
// int [] arr = {1,2,3,4,5,6,7,11,12,13,14,15,16,17};
int [] arr = {11,12,13,14,15,16,17,18,1,2,3,4,5,6,7,8};
boolean isOdd = (((arr.length /2) % 2) != 0)? true:false;

printArr(arr);
//First Loop
for (i = 1; i < (arr.length /2); i+=2) {
swap(arr,i,(arr.length /2) + i - 1);
}
printArr(arr);
//Second Loop
if(isOdd){
for (i = (arr.length/2)-1; i < arr.length-2; i++) {
swap(arr,i,i+1);
}
}
printArr(arr);
final int N = isOdd? (arr.length-2)/2:arr.length/2;
int itr = N;
int x=0;
for (i = 2; i <2*N && itr < 2*N; i+=2)
{
if(arr[i]> arr[itr])
{
if(i<itr) {
swap(arr,i,itr);
swap(arr,i+1, itr+1);
x++;
if(x==2)
{
itr+=2;
x=0;
}
}
}
else{
if(i>itr) {
swap(arr,i,itr);
swap(arr,i+1, itr+1);
}
}
}
printArr(arr);
}

static void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
static void printArr(int []arr){
for(int i = 0; i < (arr.length);i++){
System.out.print(arr[i]);
if (i!=arr.length-1)
System.out.print(",");
}
System.out.println();
}

ideone.com/P5aiI

Please comment on this

int a[10]={0,1,2,3,4,5,6,7,8,9};
int i,j;
int temp;
for(i=1, j=5;i<10;i+=2,j++)
{
temp=a[j];
for(int k=j-1;k>=i;k--)
a[k+1]=a[k];
a[i]=temp;
}

int a[10]={0,1,2,3,4,5,6,7,8,9};
	int i,j;
	int temp;
	for(i=1, j=5;i<10;i+=2,j++)
	{
			temp=a[j];
			for(int k=j-1;k>=i;k--)
				a[k+1]=a[k];
			a[i]=temp;
	}

#include<iostream>
#include<algorithm>

using namespace std;

void rearrange(int a[],int n,int pos)
{
if(pos == n/2) { for (int i=0;i<n;i++) cout<<a[i]; return; }
int k=0;
for(int i=pos;i<n/2;i++)
{
swap(a[i],a[k++ +(n/2)]);
}
rearrange(a,n,pos+1);
}
int main()
{
int a[]={1,3,5,7,2,4,6,8};

rearrange(a,8,1);
cin.get();
cin.ignore();
return 1;
}

void Rearrange(int a[],int n)
{
 int i,j;
 for(i=0 ; i < (n/2)-1; i++)
 {
   int k=0;
   for(j=0; j<=i; j++)
   {
    //calculating postion of elements need to be swapped
    int pos1 = (n/2)-(i+1)+k;
    int pos2 = (n/2)-(i)+k;
    //Swapping
    int temp = a[pos1];
    a[pos1] = a[pos2];
    a[pos2] = temp;
    k=k+2;
   }
 }
}

we will use a function which will take three parameter :
1.[Array](char []a)
2.[index Which need to move in rite position] (int i)
3.[value to place at new position](char c)

we will initiate function as :
a=arrangeArray(a,1,a[n]);
This function is responsible for move index i value to the deserving place.It also copy the value of new place and call another function to place this value to its deserving place.when all places will be arrange i will become 'n' and the recursion will stop.

the function is:

char[] arrangeArray(char[]a,int i,char c)
{

int j;
char temp;

if(i<(n-1))
 {
  j=2*i;
 }

else
 {
  j=2*(i-n)+1;
 }
if(j!=n)
 {
  temp=a[j];
  a[j]=c;
  a=arrangeArray(a,j,temp);
 }
return a;
}

Hi,

I got the O(n) solution of this problem:

#include<stdio.h>
int main()
{

int n,t,i,j,t1;
int arr[100];

//n: number of elements in array.
//
scanf("%d",&n);

for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
int p,distance,count;
int ni; //new index
count=0;

for (i=1,ni=1;i<n&&count<n-2;count++)
{
//First find the distance
//based on if number is in first half or second half
//based on distance find the new index of this number.
//
if(ni<n/2){
distance=ni;
p=2*distance;
}
else{
distance=ni-n/2+1;
p=2*distance-1;
}

//swap arr[i] with arr[p].
//
t=arr[p]; arr[p]=arr[i]; arr[i]=t;

if (i==p){
i=i+2;
ni=i;
}
else
ni=p;
}

printf ("The output array is:\n");
for (i=0;i<n;i++)
{
printf ("%d ", arr[i]);
}


return 0;

}


Logic is:
Fix i on 1. Find the new index of this number. swap arr[1] with this new index. Record this new index in ni and this number is on 1. Now find the new index based on ni. and swap arr[1] with this new index. Keep doing this till you have swapped n-2 elements.

Just one trick, after some iterations correct element will come to a[1] then increment index by 2[I don't how did it work, it was just based on example of 10 element array and now I tested it works for any number of elements].

this looks to me as a very simple question, why the solutions are so long??


bool reorder(int *array,int n)
{
if(array && n)
{
for(int i=n;i<2*n;++i)
{
int temp=array[i];

for(int e=i;e>(i-n)*2+1;--e)
{
array[e]=array[e-1];
}

array[(i-n)*2+1]=temp;
}

return true;
}

return false;
}

int main(int argc, char *argv[])
{


int array[]={1,2,3,4,5,6,7,8,9,0};
int n=5;

for(int i=0;i<2*n;++i)
printf("%d,",array[i]);
printf("\n");

reorder(array,5);

for(int i=0;i<2*n;++i)
printf("%d,",array[i]);
printf("\n");
}

test input:
1,2,3,4,5,6,7,8,9,0,
test output:
1,6,2,7,3,8,4,9,5,0,

@above what is the run time of your code?
it should be O(n). Your code is not O(n).

1.create two heaps a1----an,b1----bn by index of element
2.Now delete the root of each and insert it at starting
3.repeat the 1st step again till end

complexity will be (nlogn) i think

Easy to understand code which runs in O(n^2) time

#include<stdio.h>
void swap(int *x,int *y);
int main()
{
    int a[]={1,2,3,4,5,1,2,3,4,5};
    int i,j,k;
    int count =1,noswappings=0;
    for(i=4;i>=1;i--)
    {
      for(j=i,k=0;k<count;k++,j+=2)
      {
        swap(&a[j],&a[j+1]);
        noswappings++;
      }
      
      count++;
    }
    for( i = 0;i<10;i++)
      printf("%d ",a[i]);
    
    printf("\nNo of swappings:%d",noswappings);
    getch();
    return 0;
}
void swap(int *x,int *y)
{
     int temp = *x;
     *x = *y;
     *y = temp;
}

Here is one recursive solution I propose :

consider example a1,a2,a3,a4,b1,b2,b3,b4

1. if n is even
    swap second Half of first array with first half of second array
    so it would be a1,a2,b1,b2,a3,a4,b3,b4
    and it  can be solved recursively    
    so rearrange({a1,a2,a3,a4,b1,b2,b3,b4}) = rearrange({a1,a2,b1,b2}), rearrange({a3,a4,b3,b4});
2. if n is odd (a1,a2,a3,a4,a5,b1,b2,b3,b4,b5)
    swap second Half+1 of first array with first half+1 of second array
    so it would be a1,a2,b1,b2,b3,a3,a4,a5,b4,b5
    swap bolded elements( nth and n+1 th) a1,a2,b1,b2,a3,b3,a4,a5,b4,b5
    and it  can be solved recursively by dividing in two sub parts
    rearrange({a1,a2,a3,a4,a5,b1,b2,b3,b4,b5}) = swap(b3,a3), rearrange({a1,a2,b1,b2}), rearrange({a4,a5,b4,b5});

limiting case would be
if n==2 //since the pair is in required order
return;

Time complexity analysis ( n is size of total array a+b):

T(n) = 2*T(n/2) + n/4   ( n/4 is swapping time of second Half of first array with first half of second array)

T(n) = 2^k T(1) + n/4( 1+1/2+1/4+.......+1/(2^k))
= 2^k+n/4( 1-1/(2^k))*2                k = log(n)
=n+ (n-1)/2
=O(n)

This will work if element are of int/char/float types

#define SWAP(X,Y) (X=X^Y;Y=X^Y;X=X^Y;)

arrayChange(int a[]){
int size = sizeof(a)/sizoof(a[0]);
int i = 0;
while(i < size/2){
SWAP(a[i++], a[size-- - 1]);
}
}
size--;
}
}

#include<stdio.h>
#include<iostream>
using namespace std;
int main(int argc, char*argv[])
{
int a[] = {1,2,3,4,5,6,11,22,33,44,55,66};
int n = 6;
int temp1 = 0;
int temp2 = 0;
int changed = 2;
for(int i =1;(i<n)&&(changed!=2*n);i=i+2)
{
int start = i;
int oldIndex = i;
int newIndex = 0;
temp1 = a[oldIndex];
while(start!=newIndex)
{
if(oldIndex>=n)
{
newIndex = 2*(oldIndex-n)+1;
}
else
{
newIndex = 2*oldIndex;
}

temp2 = a[newIndex];
a[newIndex] = temp1;
changed++;
temp1 = temp2;
oldIndex = newIndex;
}
//a[start] = temp1;
}
for(int i=0;i<2*n;i++)
{
printf("%d ",a[i]);
}
printf("\n");
}

package arrays;

public class Exchange {
	public static void exchange(int[] a){
		exchange(a, (a.length/2) - 1, a.length/2);
	}
	
	private static void exchange(int[] a,int x,int y){
		if(x==0 || y==a.length-1){
			return;
		}
		
		for(int i=x;i<=y;i=i+2){
			int temp = a[i];
			a[i] = a[i+1];
			a[i+1] = temp;
		}
		exchange(a, x-1, y+1);
	}
	
	public static void main(String[] args){
		int[] a = {1,2,3,4,5,6,7,8,9,10};
		exchange(a);
		for(int i : a){
			System.out.print(i + " ");
		}
	}
}

Output: 1 6 2 7 3 8 4 9 5 10

package arrays;

public class Exchange {
	public static void exchange(int[] a){
		exchange(a, (a.length/2) - 1, a.length/2);
	}
	
	private static void exchange(int[] a,int x,int y){
		if(x==0 || y==a.length-1){
			return;
		}
		
		for(int i=x;i<=y;i=i+2){
			int temp = a[i];
			a[i] = a[i+1];
			a[i+1] = temp;
		}
		exchange(a, x-1, y+1);
	}
	
	public static void main(String[] args){
		int[] a = {1,2,3,4,5,6,7,8,9,10};
		exchange(a);
		for(int i : a){
			System.out.print(i + " ");
		}
	}
}

Output: 1 6 2 7 3 8 4 9 5 10

//given an array [a1,a2,a3...,an,b1,b2...bn], change it to [a1,b1,a2,b2.....an,bn], solution should be in-place
public static void exchange(int[] array, int n) {
int y = array.length - 1;
for (int x = n - 1; x >= 0; x--, y -= 2) {
int temp = array[x];
int j;
for (j = x + 1; j < y; j++) {
array[j - 1] = array[j];
}
array[j - 1] = temp;
}
}

What do you think guys about this solutions.
Put all the a0 to an in two queues
Now remove alternately from queue1 and queue1 and place it in the original array.

<pre lang="" line="1" title="CodeMonkey51925" class="run-this">#include "stdafx.h"

int func(int index,int len)
{
if(index<len/2)
return 2*index;
else
return (2*index-len+1);
}
int main()
{
int a[]={1,2,3,4,5,6,7,8,9,10,11,12};
int count =0,hold=a[1],temp,index=1;
int length = 12;
while(count<(length-2))
{
temp = hold;
hold = a[func(index,length)];
a[func(index,length)] = temp;
index = func(index,length);
count++;
if(index == 1)
{
//temp = hold;
//hold = a[func(index,length)];
//a[func(index,length)] = temp;
index +=(length-count-2);
hold = a[index];
//count++;
}

}
for(index=0;index<length;index++)
printf("%d\t",a[index]);

return 0;
}

</pre><pre title="CodeMonkey51925" input="yes">
</pre>

<pre lang="" line="1" title="CodeMonkey39796" class="run-this">class TestNumber {

public static void main(String[] args) {
String[] strAr = {"a1","a2","a3","a4","a5","b1","b2","b3","b4","b5"};
String[] sortAr = new String[strAr.length];
int j =0;
int k=strAr.length/2;
int m=0;
for(int i=0;i<strAr.length;i++){
if(i%2 == 0){
sortAr[j++]=strAr[m++];
}else{
sortAr[j++]=strAr[k++];
}
}

for(String str: sortAr){
System.out.println(str);
}
}
}

</pre>

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>

using namespace std;

char str[100] ;
int l ;
int global ; 

void func(int idx , char ch1 ,char ch2)
{
	if(idx == l/2)
		return ;
	ch1 = str[idx] ; 
	ch2 = str[idx + l/2] ; 
	func(idx + 1 , ch1 , ch2);
	str[global] = ch2 ; 
	str[global -1] = ch1 ; 
	global -= 2 ;
	return ;
}

int main()
{
	scanf("%s",str);
	l = strlen(str);
	global = l - 1;

	func(0,'\0','\0');

	printf("%s\n",str);
	return 0;
}

Here's my implementation with O(n) in time & space

#include <string.h>
#include <iostream>
using namespace std;
void exchange(int * a, int n) {
  int start =1;
  int tmp;
  int i,j;
  char done[n];
  memset ( done, 0, n);
  while ( start < n/2)
  { tmp = a[start];
    i = start;
    while (1)
    {
      if ( i%2 )
          j = ( n + i - 1 ) / 2;
      else
          j = i / 2;
      if ( j == start )
        break;
      a[i] = a[j];
      done[i] = 1;
      i = j;
    } 
    a[i] = tmp;
    done[i] = 1;
    while ( done[start] && start < n/2)
      ++start;
  }
}
int main()
{
  int a[2000];
  int N;
  cout << "Enter N" << endl;
  cin >> N;
  cout << "Enter the elements"<< endl;
  for ( int i = 0 ; i < N ; i++ )
    cin >> a[i];
  exchange ( a, N );
  for ( int i = 0 ; i < N ; i++)
    cout << a[i] << " ";
  cout << endl;
}

Here's my implementation with O(n) in time & space

#include <string.h>
#include <iostream>
using namespace std;
void exchange(int * a, int n) {
  int start =1;
  int tmp;
  int i,j;
  char done[n];
  memset ( done, 0, n);
  while ( start < n/2)
  { tmp = a[start];
    i = start;
    while (1)
    {
      if ( i%2 )
          j = ( n + i - 1 ) / 2;
      else
          j = i / 2;
      if ( j == start )
        break;
      a[i] = a[j];
      done[i] = 1;
      i = j;
    } 
    a[i] = tmp;
    done[i] = 1;
    while ( done[start] && start < n/2)
      ++start;
  }
}
int main()
{
  int a[2000];
  int N;
  cout << "Enter N" << endl;
  cin >> N;
  cout << "Enter the elements"<< endl;
  for ( int i = 0 ; i < N ; i++ )
    cin >> a[i];
  exchange ( a, N );
  for ( int i = 0 ; i < N ; i++)
    cout << a[i] << " ";
  cout << endl;
}

Here's my implementation with O(n) in time & space

#include <string.h>
#include <iostream>
using namespace std;
void exchange(int * a, int n) {
  int start =1;
  int tmp;
  int i,j;
  char done[n];
  memset ( done, 0, n);
  while ( start < n/2)
  { tmp = a[start];
    i = start;
    while (1)
    {
      if ( i%2 )
          j = ( n + i - 1 ) / 2;
      else
          j = i / 2;
      if ( j == start )
        break;
      a[i] = a[j];
      done[i] = 1;
      i = j;
    } 
    a[i] = tmp;
    done[i] = 1;
    while ( done[start] && start < n/2)
      ++start;
  }
}
int main()
{
  int a[2000];
  int N;
  cout << "Enter N" << endl;
  cin >> N;
  cout << "Enter the elements"<< endl;
  for ( int i = 0 ; i < N ; i++ )
    cin >> a[i];
  exchange ( a, N );
  for ( int i = 0 ; i < N ; i++)
    cout << a[i] << " ";
  cout << endl;
}

Meh, O(n^2).

#include <vector>
#include <iostream>

std::vector<int> &uninterleave(std::vector<int> &vec) {
    int n = vec.size() / 2;
    for (int i = 0; i < n-1; ++i) {
        int start = (vec.size() - 2*i - 1) / 2;
        int end   = (vec.size() + 2*i) / 2;

        for (int j = start; j < end; j += 2) {
            int temp = vec[j];
            vec[j] = vec[j+1]; 
            vec[j+1] = temp;
        }
    }

    return vec;
}

int main() {
    std::vector<int> vec{0, 1, 2, 3, 0, 1, 2, 3};

    for (auto it : vec) {
        std::cout << it << " ";
    }
    std::cout << std::endl;

    uninterleave(vec);

    for (auto it : vec) {
        std::cout << it << " ";
    }
    std::cout << std::endl;

    return 0;
}

package com.aa.array;

public class SortedOutPut {

/**
* @param args
*/
public static void main(String[] args) {
String a [] = new String[] {"a1","a2","a3","a4","a5","a6","b1","b2","b3","b4","b5","b6"};

int n= a.length;
int j =n/2;
for(int i=0 ; i < n ; i+=2){
String tmp= a[j];
shift(a,i+1,(j));
a[i+1]=tmp;
j++;
}
for(int i=0 ; i < n ; i++){
System.out.println(a[i]);
}
}

private static void shift(String[] a, int i, int j) {
for(int k = j ; k >=i ; k-- ){
a[k]=a[k-1];
}

}

}

a very simple method. o(n) time and o(1) space.
assume the array
1. scan through n,n+1,...,2*n to move each bi to the right position.
2. scan through 1,3,5,7,...,2*n-1 to move each ai to the right position.
step 1 or 2 need swap n elements, total time o(n)

CODE:
void cross_swap(vector<string> &a){
if(a.size()<=0)
return;
assert(a.size()%2==0);
int n=a.size()/2;
int ind=-1;
for(int i=0;i<n;i++){
ind+=2;
swap(a[ind],a[i+n]);
}
int i=0;
char buf[10];
int count=1;
while(i!=a.size()-2){
string tmp=a[i];
tmp=tmp.substr(1);
int num=atoi(tmp.c_str());
if(num!=count)
swap(a[i],a[2*(num-1)]);
else
i+=2,count++;
}
}

void do_this(int a[], int n)
if (n==0) return ;
for (int i=n; i >=2; i--)
swap(a[i], a[i-1]);
do_this(a+2, n-1);
}

int* algo(int *a,int size)
{
	int n=size/2;
	int j=n+1;
	int i=2;
	int temp=0;
	int temp2=0;
	while(i<2*n)
	{
		temp=j-i;
		temp2=j;
		while(temp !=0)
		{
			swap(a,temp2,temp2-1);
			temp2--;
			temp--;
		}
		j++;
		i=i+2;
	}
	retur

s = array.length / 2;
for( int i =1; i < s; i++)
swap( array[i], array[n+i-1] )

import java.util.ArrayList;
import java.util.Arrays;


public class FindSingleDuplicate {


public static void main(String[] args) {

int[] arr = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};

System.out.println("Before shifting the elements::" +Arrays.toString(arr));
arr = sort(arr);
System.out.println("After shifting the elements::"+Arrays.toString(arr));
}

private static int[] sort(int[] arr) {


int mid = (arr.length-1)/2;
for(int i=1;i<=mid;i++)
{
int count = 1;

for(int j = -(i-1);count <= i; count++)
{
arr = swap(arr,(mid+j),(mid+j+1));
j+=2;
}

}
return arr;
}

private static int[] swap(int[] arr,int i, int j) {

int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;

return arr;
}

}

Time complexity for the above is O(n*n)

Is this solution's time complexity O(n)?

public void swapElements(List<String> input) {
		
		List<String> finalList = new ArrayList<String>();
		
		List<String> firstList = input.subList(0, input.size() / 2);
		Iterator<String> firstIterator = firstList.iterator();
		List<String> secondList = input.subList(input.size() / 2, input.size());
		Iterator<String> secondIterator = secondList.iterator();
		String values = "";
		String currentValue = "";
		
		for(int i = 0; i < input.size(); i++) {			
			currentValue = i % 2 == 0 ? firstIterator.next().toString() : secondIterator.next().toString();
			finalList.add(currentValue);
			values += currentValue+" ";
		}
		
		System.out.println(values);
	}

The first technique works fine:
Successively keep swapping pairs from the middle.

void arrangeArray(int *a){
	int num_swaps = 1; //number of swaps to be done
	int i = 0;
	int mid=0;
	int swap_start_idx = 0;
	int swap_end_idx = 0;
	int temp=0;

	//find lenght of array
	while(a[i] != '\0'){
		i++;
	}
	mid = i/2 -1;
	cout << "mid: " << mid << endl;
	i=0;
	while(a[i] != '\0'){
		cout << a[i] << endl;
		i++;
	}

	while(mid -num_swaps +1 > 0){
		swap_start_idx = mid-num_swaps+1;
		swap_end_idx = mid+num_swaps;
		//cout << "num_swaps: " << num_swaps << " swap_start_idx " << swap_start_idx << "  swap_end_idx "<< swap_end_idx << endl;
		while(swap_end_idx > swap_start_idx){
			temp=a[swap_start_idx];
			a[swap_start_idx]=a[swap_start_idx+1];
			a[swap_start_idx+1] = temp;
			//cout << "a[swap_start_idx]: " <<  a[swap_start_idx] << "  a[swap_end_idx]: " << a[swap_end_idx] << endl; 
			swap_start_idx += 2;
		}
		num_swaps++;
		//cout << "num_swaps" << num_swaps << endl;
	}
	return;
}

The first technique works fine:
Successively keep swapping pairs from the middle.

void arrangeArray(int *a){
	int num_swaps = 1; //number of swaps to be done
	int i = 0;
	int mid=0;
	int swap_start_idx = 0;
	int swap_end_idx = 0;
	int temp=0;

	//find lenght of array
	while(a[i] != '\0'){
		i++;
	}
	mid = i/2 -1;
	cout << "mid: " << mid << endl;
	i=0;
	while(a[i] != '\0'){
		cout << a[i] << endl;
		i++;
	}

	while(mid -num_swaps +1 > 0){
		swap_start_idx = mid-num_swaps+1;
		swap_end_idx = mid+num_swaps;
		//cout << "num_swaps: " << num_swaps << " swap_start_idx " << swap_start_idx << "  swap_end_idx "<< swap_end_idx << endl;
		while(swap_end_idx > swap_start_idx){
			temp=a[swap_start_idx];
			a[swap_start_idx]=a[swap_start_idx+1];
			a[swap_start_idx+1] = temp;
			//cout << "a[swap_start_idx]: " <<  a[swap_start_idx] << "  a[swap_end_idx]: " << a[swap_end_idx] << endl; 
			swap_start_idx += 2;
		}
		num_swaps++;
		//cout << "num_swaps" << num_swaps << endl;
	}
	return;
}

The first technique works fine:
Successively keep swapping pairs from the middle.

void arrangeArray(int *a){
	int num_swaps = 1; //number of swaps to be done
	int i = 0;
	int mid=0;
	int swap_start_idx = 0;
	int swap_end_idx = 0;
	int temp=0;

	//find lenght of array
	while(a[i] != '\0'){
		i++;
	}
	mid = i/2 -1;
	cout << "mid: " << mid << endl;
	i=0;
	while(a[i] != '\0'){
		cout << a[i] << endl;
		i++;
	}

	while(mid -num_swaps +1 > 0){
		swap_start_idx = mid-num_swaps+1;
		swap_end_idx = mid+num_swaps;
		//cout << "num_swaps: " << num_swaps << " swap_start_idx " << swap_start_idx << "  swap_end_idx "<< swap_end_idx << endl;
		while(swap_end_idx > swap_start_idx){
			temp=a[swap_start_idx];
			a[swap_start_idx]=a[swap_start_idx+1];
			a[swap_start_idx+1] = temp;
			//cout << "a[swap_start_idx]: " <<  a[swap_start_idx] << "  a[swap_end_idx]: " << a[swap_end_idx] << endl; 
			swap_start_idx += 2;
		}
		num_swaps++;
		//cout << "num_swaps" << num_swaps << endl;
	}
	return;
}

But a better O(n) solution is that
new idx = (old idx * 2)/(num_elements - 1)

//working C++ code

void arrangeArrayVer2(int *a){
	int i = 1;
	int len = 0;
	int swap_pos = 0;
	while(a[len] != '\0'){
		len++;
	}
	cout << "length: " << len << endl;
	if(len <= 2){
		cout << "length too small, no need to rearrange" << endl;
	}
	
	int b[len];
	i = 0;
	b[0] = a[0];
	b[len-1] = a[len-1];
	while(i < len - 1){
		//ith element, new pos = 2*i/len-1;
		swap_pos = (2*i)%(len-1);
		cout << "i: " << i << " swap_pos: " << swap_pos << endl;
		b[swap_pos] = a[i];
		i++;
	}
	cout << "original array:" << endl;
	i=0;
	while(a[i] != '\0'){
		cout << a[i] << endl;
		i++;
	}
	
	cout << "rearranged array:" << endl;
	i=0;
	while(b[i] != '\0'){
		cout << b[i] << endl;
		i++;
	}
	return;
}

Good!

private static void interSwap(){
		String[] array = {"a1","a2","a3", "a4", "a5", "b1", "b2", "b3","b4","b5"};
		
		for(int i=0; i<array.length/2-1; i++) {
			int m = array.length/2 - i;
			for(int j=0; j<i+1; j++) {
				String temp = array[m];
				array[m] = array[m-1];
				array[m-1] = temp;
				m = m+2;
			}
		}
	}

Implementation and Test code.
This one is O(n) complexity,

#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;

class testInput
{
public:
	testInput(int n)
	{
		count = n;
		input.resize(2*n);

		for(int i = 0; i<n; i++)
		{
			input[i]	= i*2;
			input[i+n]	= (i*2+1);
		}
		cout<<"input:"<<endl;

		for(int i = 0; i<n; i++)
		{
			cout<<input[2*i]<<" "<<input[2*i+1]<<" ";
		}	
		cout<<endl;
		for(int i = 1; i<2*n-1; i++)
		{
			input[i] *= -1;
		}	
		cout<<"result:"<<endl;
		run();
		cout<<endl;
	}


	int mapindex(int a,int n,int q)
	{
		int i = a/n;
		int j = a%n;
		return i + j*q;
	}

	void run()
	{
		for(int it = 0; it<count;it++)
		{
			int tmp = input[it];
			if( tmp > 0)
				continue;
			int src = mapindex(it,2,count);
			int dst = it;

			while(src!=it)
			{
				input[dst] = -input[src];
				dst = src;
				src = mapindex(src,2,count);
			}
			input[dst] = -tmp;
		}
		
		for(int i = 0; i<count; i++)
		{
			cout<<input[2*i]<<" "<<input[2*i+1]<<" ";
		}	

		cout<<endl;
	}
	int count; 
	vector<int> input;
};

int _tmain(int argc, _TCHAR* argv[])
{

	testInput a(5);
	testInput b(20);
	testInput c(30);
	testInput c(100);
	return 0;
}

Use the idea A1(A2'B1')'B2=A1B1A2B2
Do it recursively,time complexity will be O(nlogn)

Use the idea A1(A2'B1')'B2=A1B1A2B2
Do it recursively,time complexity will be O(nlogn)

static void rearrange(string[] s)
        {         
            char[] str = s.ToCharArray();
            int len = s.Length;
            int[] v = new int[len];
            len--;
            v[0] = 0;
            v[len] = len;
            for(int i=0;i<len;i++)
                v[i]=(i*2)%len;

            int k=1;
            int temp=v[k];
            int count=0;
            while(k<len)
            {
                if(k==temp)
                {
                    k++;
                    temp=v[k];
                }
                else
                {
                    Swap<char>(ref str[k],ref str[temp]);
                    Swap<int>(ref v[k],ref v[temp]);
                    temp=v[k];
                }
            }
        }

        static void Swap<T>(ref T lhs, ref T rhs)
        {
            T temp;
            temp = lhs;
            lhs = rhs;
            rhs = temp;
        }

here's one possible solution. I can't really claim but it runs in o(n) time. I have tried it for array size as big as 5000, n the loop always executed a little less than 2*N times.
The idea is to calculate the expected position of the array elements and store them. While swapping elements also swap the expected positions.

private static void ReArrangeAlternte(int[] input)
        {
            int n = input.Length;
            for (int i = 1; i < n / 2; i++)
            {
                int start = n / 2 - i;
                int end = n / 2 + i;
                for (int j = start; j < end; j += 2)
                {
                    int tmp = input[j];
                    input[j] = input[j + 1];
                    input[j + 1] = tmp;
                }
            }
        }

I came up with is solution

def main():
    l = ["a1", "a2", "a3", "a4", "a5", "b1", "b2", "b3", "b4", "b5"]
    # # [a1 a2 a3 a4 a5] [b1 b2 b3 b4 b5]

    l1 = []
    l2 = []
    j = t = len(l)//2
    i = 0
    while i != t:
        l1.append(l[i])
        l2.append(l[j])
        j += 1
        i += 1
    print(l1, l2)
    l = []
    for i in range(len(l1)):
        l.append(l1[i])
        l.append(l2[i])
 
    print(l)

main()

def main():
    l = ["a1", "a2", "a3", "a4", "a5", "b1", "b2", "b3", "b4", "b5"]
    # [a1 a2 a3 a4 a5] [b1 b2 b3 b4 b5]
    l1 = []
    l2 = []
    j = t = len(l)//2
    i = 0
    while i != t:
        l1.append(l[i])
        l2.append(l[j])
        j += 1
        i += 1
    print(l1, l2)
    l = []
    for i in range(len(l1)):
        l.append(l1[i])
        l.append(l2[i])

    print(l)

main()

def main():
    l = ["a1", "a2", "a3", "a4", "a5", "b1", "b2", "b3", "b4", "b5"]
    # [a1 a2 a3 a4 a5] [b1 b2 b3 b4 b5]

    l1 = []
    l2 = []
    j = t = len(l)//2
    i = 0
    while i != t:
        l1.append(l[i])
        l2.append(l[j])
        j += 1
        i += 1
    print(l1, l2)
    l = []
    for i , j in zip(l1, l2):
        l.append(i)
        l.append(j)

    print(l)

main()

this should be n.Log(n)

lIndex3 = myArray.Length / 2;//Length is always an even number
            lIndex2 = 1;//1st position to start swapping

            for (lIndex = 0; lIndex < myArray.Length; lIndex++)
            {
                if (lIndex3 == myArray.Length - 1)
                {
                    break;
                }
                else
                {
                    swapVariable = myArray[lIndex3];

                    //shift all the elements by one place
                    if (lIndex2 >= lIndex3)//not required, only for peace of mind
                    {
                        break;
                    }
                    for (lIndex4 = lIndex3; lIndex4 >= lIndex2; lIndex4--)
                    {
                        myArray[lIndex4] = myArray[lIndex4 - 1];
                    }
                    myArray[lIndex2] = swapVariable;
                }

                lIndex3 = lIndex3 + 1;
                lIndex2 = lIndex2 + 2;
            }

import java.util.Arrays;

public class ArrayShuffle {

	public ArrayShuffle() {
	}
	
	static void shuffleArray(int a[], int n, int m) {
		if (n == a.length/2)
			return;
		
		int ncopy = n;
		int i = m - (ncopy - 1);
		int j = i + 1;
		while (ncopy != 0) { 
			swap(a, i,j);
			i += 2;
			j += 2;
			ncopy--;
		}
		shuffleArray(a, ++n, m);
	}
	
	static void swap(int a[], int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
	
	public static void main(String[] args) {
		int a[] = {1,2,3,4,5,6,7,8};
		int m = (0 + a.length-1)/2;
		shuffleArray(a, 1, m);
		System.out.println(Arrays.toString(a));
	}

}

import java.util.Arrays;

public class ArrayShuffle {

	public ArrayShuffle() {
	}
	
	static void shuffleArray(int a[], int n, int m) {
		if (n == a.length/2)
			return;
		
		int ncopy = n;
		int i = m - (ncopy - 1);
		int j = i + 1;
		while (ncopy != 0) { 
			swap(a, i,j);
			i += 2;
			j += 2;
			ncopy--;
		}
		shuffleArray(a, ++n, m);
	}
	
	static void swap(int a[], int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
	
	public static void main(String[] args) {
		int a[] = {1,2,3,4,5,6,7,8};
		int m = (0 + a.length-1)/2;
		shuffleArray(a, 1, m);
		System.out.println(Arrays.toString(a));
	}

}

var og = ['a1','a2','a3','a4','a5','b1','b2','b3','b4','b5'];
  var a = og.slice(0, og.length / 2);
  var b = og.slice(og.length / 2, og.length);
  var ordered = [];
  
  for(var i = 0; i < a.length; i++) {
    ordered.push(a[i]);
    ordered.push(b[i]);
  }
  
  console.log(ordered.join(','));

Here is a solution

#include <bits/stdc++.h>
    using namespace std;
    void Interleave(string s)
    {
    int left = 1;
    int right = s.length()/2;
    int temp;
    while (left < right)
    {
    for (int i = right; i > left; i--)
    {
    temp = s[i];
    s[i] = s[i - 1];
    s[i - 1] = temp;
    cout<<s<<endl;
    }
    left += 2;
    right += 1;
    }
    cout<<s<<endl;
    }
    int main(){
     string s="abcdefgh";
     Interleave(s);
     return 0;
    }

Output ::
abcedfgh
abecdfgh
aebcdfgh
aebcfdgh
aebfcdgh
aebfcgdh
aebfcgdh

This was pretty challenging. But fun! Here is my solution:

public class Interleave {

    // O(n log n)
    public void interleave(Object[] a) {
        if (a == null || a.length <= 2) return;
        if (a.length % 2 == 1) throw new IllegalArgumentException("Must be an even number of pairs");

        split(a, 0, a.length-1);
    }

    private void split(Object[] a, int left, int right) {
        int size = right-left+1;
        if (size <= 2) return;

        int mid = left + (size/2);

        // Pretty ugly in terms of time complexity, adds O(size/2).
        // As an optimization, instead of checking for multiples of 4,
        // check for powers of 2, and slide over that way.
        // 0 1 2 3  4  5  6  7  8  9 10 11 12 13 14 15 16 17
        // x x x x a3 a4 a5 a6 a7 a8 a9 b3 b4 b5 b6 b7 b8 b9
        // size is 14
        // swap indicies 10 and 16
        // move right index from 17 to 15
        if ((size % 4) != 0) {
            // e.g., size is 14, swap 10th with 16th
            shift(a, mid-1, mid, size/2-1);
            right = right - 2;
            size = size - 2;
            mid = mid - 1;
        }

        // slide over the third quarter to the second quarter
        shift(a, left + (mid - left) / 2, mid, size/4);

        // O(log n)
        split(a, left, mid-1);
        split(a, mid, right);
    }

    // O(count)
    private void shift(Object[] a, final int to, final int from, final int count) {
        int i = to;
        int j = from;
        int counter = 0;
        while (counter < count) {
            swap(a, i++, j++);
            counter++;
        }
    }

    // O(1)
    private void swap(Object[] a, int i, int j) {
        Object temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }


}

For Python3 this is what I did:

_input = ['a1','a2','a3','a4','a5','b1','b2','b3','b4','b5']
a = _input[:int(len(_input)/2)]
b = _input[int(len(_input)/2):]
d = []

for a,b in zip(a,b):
d.append(a)
d.append(b)

print(d)

There might be another way to simplify it, I couldn't find it.

#sort by swapping approach
import numpy as np
N= 40

giv_arr = ["a"+str(i) for i in range(1,N+1)] + ["b"+str(i) for i in range(1,N+1)]
print(giv_arr)
def swap(X,Y):
X,Y = Y,X

def check_is_leser(X,Y):
x = int(X[1:])
y = int(Y[1:])
return x < y

def sort_swapmiddle(A):
#get the mid point
N = len(A)//2

#Check if swap happened
swapped = True
itr = 0
#Only when swap happened else stop
while swapped:
#mark as not swapped
swapped = False
#initialize index
L = N-1 #end of first array
R = N #start of second array
i = 0 #iteration counter
if check_is_leser(A[R],A[L]): #only one swap for the edge of the arrays
A[L],A[R] = A[R],A[L]
swapped = True
itr += 1

while check_is_leser(A[L-i],A[L-i-1]): #Track only left array , break when the minimum is reached.
swapped = True
itr += 1
#Swap the right and left element
A[L-i-1],A[L-i] = A[L-i],A[L-i-1]
A[R+i],A[R+i+1] = A[R+i+1], A[R+i]
i += 1

print(itr)
return A

print(sort_swapmiddle(giv_arr))