# Optimize algorithm arrange an array with items with even-indexs are on left side

• December 1st, 2015, 04:50 AM
hongchanphat
Optimize algorithm arrange an array with items with even-indexs are on left side
Optimize algorithm arrange an array with items with even-indexs are on left side of array, items with odd-indexs are on right side of array

Requirement: using recursion, size of array is an even number.

For example:
0 1 2 3 4 5 (order of index)
a b c d e f (array before arrange)
a c e b d f (array after arrange)

0......1......2......3.....4......5.....6......7 (order of index)
a1....b1....a2....b2....a3....b3....a4....b4 (array before arrange)
a1....a2....a3....a4....b1....b2....b3....b4 (array after arrange)

The problem looks easy to solve if we dont care about optimization, we can use temp array or use recursion combine with a loop to shift items ... I think this way is not best solution ....I try to use recursion combine with swap operation, without using loop ... but I fail.

Hope someone suggests me an idea to resolve the problem, thanks any help
• December 3rd, 2015, 12:44 AM
tiliavirga
Re: Optimize algorithm arrange an array with items with even-indexs are on left side
Quote:

Originally Posted by hongchanphat
or use recursion combine with a loop to shift items ... I think this way is not best solution

To recursively split the array into halves and re-arrange items would correspond to the idea behind quicksort.

And you could use sorting here. It's just to impose an ordering on the items and sort the array. Maybe that's cheating but it would give you an O(N * logN) solution. If you want better you must aim for O(N) which basically means you need to find a solution that scans the array a certain number of times independent of the number of items. This is not possible in the general case but since the array has a specific initial ordering this case may be an exception.