-
December 1st, 2015, 04:50 AM
#1
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
#2
Re: Optimize algorithm arrange an array with items with even-indexs are on left side
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.
Last edited by tiliavirga; December 3rd, 2015 at 07:04 PM.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|