Arranging by indexes vector

Question

I have two vectors: a vector and index vector. How can I make the vector be arranged by the indexes vector? Like:

Indexes                5 0 2 1 3 4
Values                 a b c d e f
Values after operation b d c e f a

The indexes vector will always contain the range [0, n) and each index only once.
I need this operation to be done in place because the code is going to be run on a device with low memory.
How can I do this in c++? I can use c++11

Answer 1

Since you know that your index array is a permutation of [0, N), you can do this in linear time and in-place (plus one temporary) by working cycle-by-cycle. Something like this:

size_t indices[N];
data_t values[N];

for (size_t pos = 0; pos < N; ++pos)  // \
{                                     //  }  this loops _over_ cycles
  if (indices[pos] == pos) continue;  // /

  size_t i = pos;
  const data_t tmp = values[pos];

  while (true)                        // --> this loops _through_ one cycle
  {
    const size_t next = indices[i];
    indices[i] = i;
    values[i] = values[next];

    if (next == pos) break;
    i = next;
  }

  values[i] = tmp;
}

This implementation has the advantage over using swap each time that we only need to use the temporary variable once per cycle.

If the data type is move-only, this still works if all the assignments are surrounded by std::move().

Answer 2

for(int i=0;i<=indexes.size();++i)
 for(int j=i+1;j<=indexes.size();++j)
             if(indexes[i] > indexes[j] )
                       swap(indexes[i],indexes[j]),
                       swap(values[i],values[j]);

It's O(N²) complexity, but should work fine on small number values.

You can also pass a comparison function to the C++ STL sort function if you want O(N*logN)

Answer 3

std::vector<int>  indices = { 5,   0,   2,   1,   3,   4};
std::vector<char> values  = {'a', 'b', 'c', 'd', 'e', 'f'};

for(size_t n = 0; n < indices.size(); ++n)
{
    while(indices[n] != n)
    {
        std::swap(values[n],  values[indices[n]]);
        std::swap(indices[n], indices[indices[n]]);
    }
}

EDIT:

I think this should be O(n), anyone disagree?

Answer 4

You can just sort the vector, your comparison operation should compare the indices. Of course, when moving the data around, you have to move the indices, too.

At the end, your indices will be just 0, 1, ... (n-1), and the data will be at the corresponding places.

As implementation note: you can store the values and indices together in a structure:

struct SortEntry
{
    Data value;
    size_t index;
};

and define the comparison operator to look only at indices:

bool operator< (const SortEntry& lhs, const SortEntry& rhs)
{
    return lhs.index < rhs.index;
}

Answer 5

This solution runs in O(n) time:

int tmp;
for(int i = 0; i < n; i++)
  while(indexes[i] != i){
    swap(values[i], values[indexes[i]]);
    tmp = indexes[i];
    swap(indexes[i], indexes[tmp]);
  }

Answer 6

This will run in O(n) time without any error.Check it on ideone

int main(int argc, char *argv[])
{
int indexes[6]={2,3,5,1,0,4};
char values[6]={'a','b','c','d','e','f'};
int result[sizeof(indexes)/4];          //creating array of size indexes or values
int a,i;
for( i=0;i<(sizeof(indexes)/4);i++)
{
    a=indexes[i];                       //saving the index value at i of array indexes
    result[a]=values[i];                //saving the result in result array
 }
 for ( i=0;i<(sizeof(indexes)/4);i++)
   printf("%c",result[i]);              //printing the result
   system("PAUSE"); 
   return 0;
}