Algorithms: In-place algorithm to rearrange elements of an array

C++In a given array of elements like
[a1, a2, ..., an, b1, b2, ..., bn, <X>1,<X>2, ..., <X>n]

without taking a extra memory swap elements in the array so the outcome will be like
[a1, b1, … <X>1, a2, b2, … <X>2, …, an, bn, …, <X>n]

Solution 1

  1. Prepare an array with X groups with N elements.
  2. Process first two groups
    1. Divide these groups into four sections:[X,Y|A,B]
    2. Swap these sections so the outcome will be [X,A|Y,B].
    3. Continue recursively until A=B (right part contains one element only)
    4. Consider the processed parts as ONE group for the next processing.
    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.

 For example:

  1. Array = [1,2,3,4,5,6,7,8,a,b,c,d,e,f,g,h]
  2. FIRST = [1,2,3,4,5,6,7,8], SECOND = [a,b,c,d,e,f,g,h]
    1. X = [1,2,3,4], Y = [5,6,7,8], A = [a,b,c,d], B = [e,f,g,h]
    2. Array = [1,2,3,4,a,b,c,d,5,6,7,8,e,f,g,h]
      [X|A] = [1,2,3,4,a,b,c,d]
    3. U = [1,2], V = [3,4], W = [a,b], Z = [c,d]
      Swap V and W:[U,W|V,Z] = [1,2,a,b,3,4,c,d]
      [U|W] = [1,2,a,b] swap 2 and a:
      [1,a,2,b]

Solution 2

  • Process all array groups from back to front
  • From the currently being processed group, save the last item to temp variable, rotate the array from position 0, to the item being processed and set the temp variable as first item of the array
  • Continue until all items are processed
  • This approach is called in-place “matrix transposition”

Example

  • ARRAY = [A,B,C,1,2,3,X,Y,Z]
  • ARRAY = [Z,A,B,C,1,2,3,X,Y]
  • ARRAY = [3,Z,A,B,C,1,2,X,Y]
  • ARRAY = [C,3,Z,A,B,1,2,X,Y]
  • ARRAY = [Y,C,3,Z,A,B,1,2,X]
  • ARRAY = [2,Y,C,3,Z,A,B,1,X]
  • ARRAY = [B,2,Y,C,3,Z,A,1,X]
  • ARRAY = [X,B,2,Y,C,3,Z,A,1]
  • ARRAY = [1,X,B,2,Y,C,3,Z,A]
  • ARRAY = [A,1,X,B,2,Y,C,3,Z]

I tried to implement this solution in C++ so who is interested, here comes the source code:

#include<iostream>
#include<vector>

using namespace std;

struct Part {
  unsigned int start;
  unsigned int end;
};

struct Bounds {
  Part first;
  Part second;
};

void printArray(vector<char>& array){
  int len = array.size();
  for(int i=0; i<len; i++)
    cout << array[i] << " ";
}

void rotateArray(vector<char>& array, int start, int end, int num_positions) {
  for(int i = 0; i < num_positions; i++) {
    char last = array[end];
    for(int j=end; j > start; j--)
      array[j] = array[j-1];
      array[start] = last;
    }
}

void swapTwoArrayParts(vector<char>& array, Bounds bounds) {
  int first_part_items = bounds.first.end - bounds.first.start + 1;
  int second_part_items = bounds.second.end - bounds.second.start + 1;;
  int factor = first_part_items / second_part_items;

  // there's nothing to sort
  if (second_part_items == 1)
    return;

  int num_rotations = second_part_items / 2;
  int rotate_start = bounds.first.start + num_rotations * factor;
  int rotate_end = bounds.second.start + num_rotations - 1;
  rotateArray(array, rotate_start, rotate_end, num_rotations);

  //swap left part
  if (num_rotations > 1){
    Bounds b;
    b.first.start = bounds.first.start;
    b.first.end = rotate_start - 1;
    b.second.start = rotate_start;
    b.second.end = rotate_start + num_rotations - 1;
    swapTwoArrayParts(array, b);
  }
  //swap right part
  if(second_part_items > 2){
    Bounds b;
    b.first.start = rotate_start + num_rotations;
    b.first.end = b.first.start + bounds.first.end - rotate_start;
    b.second.start = b.first.end + 1;
    b.second.end = bounds.second.end;
    swapTwoArrayParts(array, b);
  }
}

void swapArray(vector<char>& array, int num_groups) {
  if(array.size() % num_groups != 0)
    throw "Incorrect input data";

  int part_items = array.size() / num_groups;

  // there's nothing to sort
  if (part_items == 1)
    return;
  for(int i = 2; i <= num_groups; i++) {
    Bounds b;
    b.first.start = 0;
    b.first.end = ((i-1) * part_items) - 1;
    b.second.start = b.first.end + 1;
    b.second.end = (i * part_items) - 1;
    swapTwoArrayParts(array, b);
  }
}

/******************************************/
/* AND ANOTHER MUCH MORE ELEGANT SOLUTION */
/******************************************/
void swapArray2(vector<char>& array, int num_groups) {
  int array_size = array.size();
  int num_items = array_size / num_groups;

  for(int i=0; i<num_items; i++) 
    for(int j=0; j<num_groups; j++)
      rotateArray(array, 0, (array_size-1) - j*(num_items - (i+1)), 1);
}

void loadScenario(vector<char>& array, int* num_groups, int scenario){
  switch(scenario){
  case 1: {
    *num_groups = 3;
    array.push_back('a');
    array.push_back('b');
    array.push_back('c');
    array.push_back('d');

    array.push_back('1');
    array.push_back('2');
    array.push_back('3');
    array.push_back('4');

    array.push_back('w');
    array.push_back('x');
    array.push_back('y');
    array.push_back('z');
    }
    break;
  case 2: {
    *num_groups = 4;
    array.push_back('a');
    array.push_back('b');
    array.push_back('c');

    array.push_back('1');
    array.push_back('2');
    array.push_back('3');

    array.push_back('w');
    array.push_back('x');
    array.push_back('y');

    array.push_back('p');
    array.push_back('q');
    array.push_back('r');
    }
    break;
  case 3: {
    *num_groups = 2;
    array.push_back('a');
    array.push_back('b');
    array.push_back('c');
    array.push_back('d');
    array.push_back('e');
    array.push_back('f');
    array.push_back('g');

    array.push_back('1');
    array.push_back('2');
    array.push_back('3');
    array.push_back('4');
    array.push_back('5');
    array.push_back('6');
    array.push_back('7');
    }
    break;
  case 4: {
    *num_groups = 2;
    array.push_back('a');
    array.push_back('b');
    array.push_back('c');

    array.push_back('1');
    array.push_back('2');
    array.push_back('3');
    }
    break;
  }
}

int main(int argc, char* argv[]){
  int num_groups;
  vector<char> array;

  for(int i=1; i<=4; i++){
    array.clear();
    cout << "TEST SCENARIO: " << i << endl;
    loadScenario(array, &num_groups,i);

    cout << "Original array: " << endl;
    printArray(array);

    cout << endl << "SWAP NOW !!!" << endl;
    /* First solution */
    swapArray(array, num_groups);
    /* Second solution */
    //swapArray2(array, num_groups);

    cout << "Swapped array: " << endl;
    printArray(array);
    cout << endl<< "************************************" << endl << endl;
  }
  return 0;
}

Leave a Reply