인덱스로 정렬 벡터

Question

두 벡터 : 벡터와 인덱스 벡터가 있습니다. 벡터를 인덱스 벡터로 정렬하려면 어떻게합니까? Like :

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

색인 벡터는 항상 [0, n) 범위를 포함하며 각 색인은 한 번만 포함됩니다.
코드가 메모리가 부족한 장치에서 실행되기 때문에이 작업을 수행해야합니다.
어떻게하면 C++에서이 작업을 수행 할 수 있습니까? 나는 C++을 사용할 수있다. 11

Answer 1

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

편집 O (N * logN)를 원하는 경우는 C++의 STL 정렬 기능에 대한 비교 함수를 전달할 수 있습니다 동의하지 않는다?

Answer 2

벡터를 정렬 만하면 비교 연산이 색인을 비교해야한다. 물론, 데이터를 이동할 때 색인을 이동해야합니다.

마지막으로 색인은 0, 1, ... (n-1)이며 데이터는 해당 위치에 있습니다. 구현 참고로

: 당신이 값을 저장하고 구조에서 함께와 indices 수 있습니다

struct SortEntry 
{ 
    Data value; 
    size_t index; 
}; 

및 인덱스에서만보고 비교 연산자를 정의

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

Answer 3

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

그것은 O를의 (N²)의 복잡성을 가지지 만 소수의 값에서는 잘 작동합니다. 나는이 있어야한다 O (n)을 생각

, 사람 :

당신은 또한 당신이

Answer 4

인덱스 배열이 [0, N)의 순열이므로 순환 주기로 작업하여 선형 시간 및 그 밖의 위치 (플러스 하나)로이 작업을 수행 할 수 있습니다. 이런 식으로 뭔가 :

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

이 구현은, 우리는주기 당 일단 임시 변수 를 사용해야 할 때마다 swap 사용을 통해 장점이 있습니다.

데이터 유형이 이동 전용 인 경우 모든 할당이 std::move()으로 둘러싸여 있으면이 작업이 계속 수행됩니다.

Answer 5

이 솔루션은 O (n)이 시간에 실행됩니다

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

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