{"id":608,"date":"2013-05-30T14:58:16","date_gmt":"2013-05-30T13:58:16","guid":{"rendered":"http:\/\/oprsteny.cz\/?p=608"},"modified":"2015-02-27T14:54:25","modified_gmt":"2015-02-27T13:54:25","slug":"algorithms-in-place-algorithm-to-rearrange-elements-of-an-array","status":"publish","type":"post","link":"https:\/\/oprsteny.cz\/?p=608","title":{"rendered":"Algorithms: In-place algorithm to rearrange elements of an array"},"content":{"rendered":"

\"C++\"In a given array of elements like
\n[a1<\/sub>, a2<\/sub>, ..., an<\/sub>, b1<\/sub>, b2<\/sub>, ..., bn<\/sub>, <X>1<\/sub>,<X>2<\/sub>, ..., <X>n<\/sub>]<\/code>
\nwithout taking a extra memory swap elements in the array so the outcome will be like
\n[a<\/span>1<\/sub>, b<\/span>1<\/sub>, … <X><\/span>1<\/sub>, a<\/span>2<\/sub>, b<\/span>2<\/sub>, … <X><\/span>2<\/sub>, …, a<\/span>n<\/sub>, b<\/span>n<\/sub>, …, <X><\/span>n<\/sub>]<\/span><\/p>\n

Solution 1<\/h1>\n
    \n
  1. Prepare an array with X groups with N elements.<\/li>\n
  2. Process first two groups\n
      \n
    1. Divide these groups into four sections:[X,Y|A,B]<\/li>\n
    2. Swap these sections so the outcome will be [X,A|Y,B].<\/li>\n
    3. Continue recursively until A=B (right part contains one element only)<\/li>\n
    4. Consider the processed parts as ONE group for the next processing.<\/li>\n
    5. In case the array still contain more groups take the result group as the first group into the next loop and go to 2.<\/li>\n<\/ol>\n<\/li>\n<\/ol>\n

      \u00a0For example:<\/h2>\n
        \n
      1. Array = [1,2,3,4,5,6,7,8,<\/span>a,b,c,d,e,f,g,h<\/span>]<\/li>\n
      2. FIRST = [1,2,3,4,5,6,7,8<\/span>], SECOND = [a,b,c,d,e,f,g,h<\/span>]\n
          \n
        1. X = [1,2,3,4<\/span>], Y = [5,6,7,8<\/span>], A = [a,b,c,d<\/span>], B = [e,f,g,h<\/span>]<\/li>\n
        2. Array = [1,2,3,4,<\/span>a,b,c,d,<\/span>5,6,7,8,<\/span>e,f,g,h<\/span>]
          \n[X|A] = [1,2,3,4,<\/span>a,b,c,d<\/span>]<\/li>\n
        3. U = [1,2<\/span>], V = [3,4<\/span>], W = [a,b<\/span>], Z = [c,d<\/span>]
          \nSwap V and W:[U,W|V,Z] = [1,2,<\/span>a,b,<\/span>3,4,<\/span>c,d<\/span>]
          \n[U|W] = [1,2,<\/span>a,b<\/span>] swap 2 and a:
          \n[1,<\/span>a,<\/span>2,<\/span>b<\/span>]<\/li>\n<\/ol>\n<\/li>\n<\/ol>\n

          Solution 2<\/h1>\n