Array Rotation: Dolphin Algorithm: Dolphin Algorithm

[This page is auto-generated; please prefer to read the article’s PDF Form.]

Dolphin Algorithm

We now move back to the discussion about sequence (1). As found in (2), the elements of sequence S_i are given by (i + jk) mod n, for j = 0,1,2,…. Let g = gcd(k,n) and t = n∕g. Using corollary 2, we can conclude this about sequence S_i for 0 ≤ i < g:

(a) the ﬁrst t elements of the sequence are all distinct, forming the set G_i = {i,g + i,2g + i,…,((n∕g) − 1)g + i}. Also, the ﬁrst element simply equals i.

(b) after the ﬁrst t elements, the subsequence of these t elements keeps repeating in the sequence S_i. That is, the (t + 1)^th element equals 1^st element (which is i), and so on.

(c) for all j ≥ 0, the (j + 1)^th element is given by (jk) mod n + i. So, the (j + 1)^th element of the g sequences S₀,S₁,…,S_g−1 are consecutive.

We will be referring to the subsequence of ﬁrst t elements of each sequence S_i as “cycle C_i”, which are nothing but elements of set G_i in some order. Note that, the t^th/last value of C_i has its target-index as the ﬁrst value of C_i; hence the name “cycle”.

What we have so far discussed forms the mathematical basis of the Dolphin Algorithm, which we describe now. For rotating the array, that is to rearrange its n elements, the algorithm considers one cycle C_i at a time, for i = 0,1,2,…,g − 1. Recall that the cycle C_i consists of t = n∕g array indices starting with i, such that each index x is followed by its target-index f(x).

The elements of array a which are located at indices of cycle C_i, can be rearranged as required by moving them as per the cycle’s order. Now, for iterating over the cycle C_i, we can either step in the forward direction as:

In the ﬁrst way, a source-index is followed by its target-index. In the second one, it is the reverse. Below method implemented in C shows a way to rearrange the elements indexed by cycle C_i using the backward iteration:

/* n added below as x-k can be negative */
#define g(x) ((x-k+n)%n)

/* Process one cycle C_i. k must satisfy: 1 <= k <= (n-1) */
void process_a_cycle(int a[], int n, int k, int i)
{
  int si, ti; /* source-index, target-index */
  int external;

  ti = i;
  si = g(ti);
  external = a[ti]; /* created a vacancy/hole at ti */

  /* loop-invariants:
       P1: ti is the target-index for si, i.e. g(ti)=si.
       P2: the hole is located at ti. */
  while(si != i)
  {
    /* fill-up the hole at ti, now creating a hole at si */
    a[ti] = a[si];
    ti = si;
    si = g(ti);
  }

  /* (P2: the hole is located at ti) holds, and ti has source-index
     (si = i) */
  a[ti] = external;
}

Notice how the elements could be shifted along the cycle while requiring extra memory for only one array element. The forward iteration can also be implemented slightly diﬀerently.

Now, due to (3) and (4) we know that if we rearrange each of the g cycles C₀,C₁,…,C_g−1 as above, we will have rearranged all the n elements of the array. So, the following method must result in rotation of the array as required. For computing the gcd, it uses Euclid’s Algorithm.

void dolphin(int a[], int n, int k)
{
  int i, g;

  g = gcd(n, k);

  for(i = 0; i < g; i++)
    process_a_cycle(a, n, k, i);
}
int gcd(const int X, const int Y)
{
  int x, y;

  x = X; y = Y;

  while(x != 0 && y != 0)
  {
    if(x > y)
      x = x%y;
    else
      y = y%x;
  }

  if(x != 0)
    return x;
  else
    return y;
}

Note that this algorithm moves each array element (except a[i]) only once, directly to its target-index, hence avoiding any intermediate moves. It was named “Dolphin Algorithm” by [2] because, “the movement of the array values looked like dolphins leaping out of the water and disappearing again at random places”.