Wednesday, November 2, 2011

Array rearranging algorithm

/*Suppose we have an array a1, a2, ..., an, b1, b2, ..., bn. Implement an algorithm to change
this array to a1, b1, a2, b2, ..., an, bn.*/ a1, b1   ok
a1, a2, b1, b2-> a1, a2<->b1, b2-> a1, b1, a2, b2 ok
a1,a2,a3,a4,b1,b2,b3,b4 -> a1 a2 (b1 b2), (a3,a4), b3, b4-> it becomes 2 subproblems of the above

//size of arr_num must be even number
void rearrange(int arr_num[], int p, int q)

if ( p == q || g == p+1) return;
int r = (q+p)/2;

//Exchange: (p+r)/2........r<----> r+1......(r+q)/2
for(int i = (p+r)/2; i
int temp= arr_num[i];
arr_num[r-1+i] = temp;

rearrange(arr_num, p, r);
rearrange(arr_num, r+1, q);


No comments: