Mutate an array order using only swap

Question

Assume you have two arrays, a and b. a's data is completely hidden from you. The only operation you can perform on a is to swap two elements. b's data is completely exposed and mutable.

The value of b at position i indicates the destination for the value stored in a[i]. That is, if b[3] = 7, we want to move the value in a[3] to be in a[7]. I'm trying to write an algorithm which mutates array a according to the information in array b using only swap operations on a (and preferably linear time and constant space). Just as an example:

if   a  = { a b c d e f }
and  b  = { 1 3 2 0 5 4 }
then a' = { d a c b f e }
(ie, a[i] = a'[b[i]])

I tried a naive approach of iterating through b and merrily doing a.Swap(i, b[i]), all the while whistling, but that turns out to end up writing over itself and moving data that's already in the right place (as you might guess).

Edit: This really must be linear time. It's for a parallel sorting algorithm, so speed is paramount.

Answer 1

Solution in Go:

for i := 0; i != len(b); i++ {
    for b[i] != i {
        a.Swap(i, b[i])
        b.Swap(i, b[i])
    }
}

This may not immediately look O(n), but notice that

• every a.Swap() puts at least one element of a into its final position
  • once an element is in its final position it never gets swapped again
  • so there are at most n swaps
• the b[i] != i test is done once for each swap and one extra time for each i
  • so there are at most 2n tests

As you can see, this algorithm is O(n) on time and O(1) on space.