How to permute array into a given order with O(1) auxiliary space?

Question

How do I implement the following OrderElements function?

char chars[] = {'a', 'b', 'c', 'd', 'e'};
int want_order[] = {2, 4, 3, 0, 1};
int length = 5;
OrderElements(chars, want_order, length);

// chars now contains: c, e, d, a, b

It's easy when you can use linear extra space, but can it be done with only constant extra space, i.e., directly sorting the chars elements in-place?

P.S.: This was not an exam question; I actually need this function.

CLARIFICATION: There seems to be a misunderstanding about the desired final order of elements. The resulting array in the example should have the following elements, referring to the original chars array:

{chars[2], chars[4], chars[3], chars[0], chars[1]}

which is

{'c', 'e', 'd', 'a', 'b'}.

Answer 1

Strictly speaking, though, O(lg length) memory is needed to represent the list index; I'm going to ignore this for this discussion, however, since using a 64-bit i is probably big enough for anything that we can actually reorder.

for (int i = 0; i < length; i++) {
  int t = want_order[i];
  while (t < i) {
    // t has been moved already; we need to find out where the value that started there
    // went. Since we must've put it at want_order[t] before, resume looking there
    t = want_order[t];
    // once t >= i, we know we've not touched that slot more than once, and so our
    // value is there
  }
  swap(chars[i], chars[t]);
}

An intuitive explanation: For each item in the array, we put the goal value in it, storing our old value in the slot that contained our goal value. We have to take care to deal with the case that our goal value was displaced; this is handled by noting that a given slot is only swapped up to twice; once when the value in there is stolen by another value (which couldn't have happened, since this iteration is going to do that) or when the value is displaced to insert the final value (which only happens to lower indices).

An illustration of how this looks on your sample data:

 i | want_order | chars     | t
 0 |  2 4 3 0 1 | a b c d e | 2 (swap)
 1 |  2 4 3 0 1 | c b a d e | 4 (swap)
 2 |  2 4 3 0 1 | c e d a b | 3 (swap)
 3 |  2 4 3 0 1 | c e d a b | 0 (follow)
 3 |  2 4 3 0 1 | c e d a b | 3 (swap - no-op)
 4 |  2 4 3 0 1 | c e d a b | 1 (follow)
 4 |  2 4 3 0 1 | c e d a b | 4 (swap - no-op)

This algorithm uses only O(lg n) memory (for the indices), but I have not attempted to fully analyze its running time. It's obvious that it's at worst O(n^2), however I suspect it will fare better than that in practice. However, there is no real bound on the length of the chains it might have to follow, so in principle it may in fact end up using O(n^2) time with worst-case input.

Answer 2

Impossible.

You need at least O(log (list size)) to know the index of the sorted element.

Answer 3

Sort Operation with Memory O(1) is Bubblesort, but it have an Performance O(n²)

http://en.wikipedia.org/wiki/Bubble%5Fsort

Answer 4

This will do the job in O(n²). In each iteration of the outer loop the currently wanted element is swapped down to its correct position (first inner loop) and then the wanted order of the remaining elements is adjusted to reflect the new situation (second inner loop).

for (int i = 0; i < length; i++)
{
    for (int j = wantedOrder[i]; j > i; j--)
    {
        Swap(chars, j, j - 1);
    }

    for (int j = i + 1; j < length; j++)
    {
        if (wantedOrder[j] < wantedOrder[i])
        {
            wantedOrder[j]++;
        }
    }
}

This of course requires destroying the wanted order array. If this is not allowed, I have no idea how to solve the problem (at least at the moment).

Answer 5

It can be done If you are allowed to change the want_order array. The algorithm is rather simple as the permutation can be decomposed into cycles. When you iterating one cycle, just mark each one being visited. And the time complexity is O(N). Pseudo code:

 char chars[] = {'a', 'b', 'c', 'd', 'e'};
 int want_order[] = {2, 4, 3, 0, 1};
 int length = 5;
 OrderElements(chars, want_order, length)
 {
    for ( i = 0; i < length; ++i )
    {
      if ( want_order[i] == -1 ) continue;

      j = startPos = want_order[i];
      c = chars[i];

      do
      {
         swap(c, chars[j]);
         j = want_order[j];
         want_order[j] = -1;
      } while( j != startPos );
    }
  }