CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2
  1. #1
    Join Date
    Dec 2015
    Posts
    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

  2. #2
    Join Date
    Jun 2015
    Posts
    208

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

    Quote Originally Posted by hongchanphat View Post
    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
  •  





Click Here to Expand Forum to Full Width

Featured