in-place permutation of a array follows this rule

Posted by Mgccl on Stack Overflow See other posts from Stack Overflow or by Mgccl
Published on 2010-06-17T15:16:27Z Indexed on 2010/06/17 16:43 UTC
Read the original article Hit count: 216

Filed under:

Suppose there is an array, we want to find everything in the odd index, and move it to the end. Everything in the even index move it to the beginning. The relative order of all odd index items and all even index items are preserved. Suppose the values of the array, a[i] = i, n is even. Then we have.

0,1,2,3,4,5,...,n-1

after the operation

0,2,4,6,...,n-2,1,3,5,7,...,n-1

Can this be done in-place and in O(n) time?

© Stack Overflow or respective owner

Related posts about algorithm