CODEWITHSUNDEEP
c++algorithm
Daniel
Daniel

Reputation: 31579

Arranging by indexes vector

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

Upvotes: 1

Views: 213

Answers (6)

ronag
ronag

Reputation: 51263

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?

Upvotes: 1

Ravi Kumar
Ravi Kumar

Reputation: 123

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;
}

Upvotes: 0

Kerrek SB
Kerrek SB

Reputation: 477368

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().

Upvotes: 3

a-z
a-z

Reputation: 1664

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]);
  }

Upvotes: 0

XCS
XCS

Reputation: 28157

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)

Upvotes: 1

Vlad
Vlad

Reputation: 35594

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;
}

Upvotes: 0

Related Questions