Rearranger

A few days ago I learnt a new algorithm to rearrange arrays.

Let’s start with two arrays as following: a1 = {1,2,3,0} , a2 = {2,3,0,1}.
Now, what we want is to rearrange the first array as the second one: the rule is that you can swap two elements only if one of them is zero.
For example: you can swap {1,0} , {2,0} , {3,0} while you can’t swap {1,2} or {3,2} etc.

Have a once-over to the algorithm step-by-step:

1. a1 = {1,2,3,0} // Initial situation
2. a1 = {0,2,3,1} // {1,0}
3. a1 = {2,0,3,1} // {2,0}
4. a1 = {2,3,0,1} // {3,0} // Final situation

As you can see, each element is swapped only with zero and the result is correct: the first array is rearranged.

Now, let’s have a look at the code (Java):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void rearrange (int[] first, int[] second) {
  /* Loop for the first array */
  for (int i = 0; i < first.length; i++) {
    /* Loop for the second array */
    for (int j = 0; j < second.length; j++) {
      /* 1 */
      if ((first[i] == second[j]) && (i != j)) {
        int k;
        /* 2 */
        for (k = 0; k < first.length; k++) {
          if (first[k] == 0) break;
        }
        /* 3 */
        first[k] = first[i];
        first[i] = 0;
        break;
      }
    }
  }
}

The algorithm is:

1. find two equal elements with different indexes
2. find the index of the zero element in the first array
3. swap them

Maybe this solution isn’t the best but it works fine.
I like this algorithm and I think it’s brilliant for certains situations: think you are in a parking and you have to move each car one per time :P