配列を別の配列の順番に並べ替えます

Question

配列B[]={6, 5, 1, 2, 4, 3};に従って並べ替える必要がある配列A[]={8, 9, 11, 14, 16, 20};があるとします。

選別A

だから A[]={20, 16, 8, 9, 14, 11};

になり、どのようにAがソートされますがBで語られています。
Bの最初の要素が最大であるため、Aの最初の要素も最大になります。 Bの第3の要素はB場合Aの最小ので、第三の要素はまた、最小の

なりで何かがAも降順にソートされます次に{100, 84, 74, 51, 5, 1}のように降順にソートされました。
例：私は、異なる年齢の何人かの友人を持っている、と私は彼らに応じて何かを与えたい場合はB = {2, 3, 45, 0, 7, 56}場合、Aは{9, 11, 16, 8, 14, 20}

そのようになり
1. B = {12, 8, 14, 156, 2, 84}場合、Aは{11, 9, 14, 20, 8, 16}
2.だろう彼らの年齢に最長の人は最大のものを得て、それより小さいものはそれよりも小さいものを得ます。

私は同様の質問を見ましたが、私の問題のようなものではありません。
私の考えは、両方を最初に並べ替えることです。そして、並べ替える。

高速なソリューションはありますか？

Answer 1

あなたの質問が正しく理解されている場合は、ソートされた順列の逆数をBとして計算し、次に並べ替え順にAを並べ替える必要があります。これは標準ライブラリで簡単に行うことができます。

int A[] = { 8, 9, 11, 14, 16, 20}; 
int B[] = { 6, 5, 1, 2, 4, 3}; 

const auto ASIZE = std::extent<decltype(A)>::value; 
const auto BSIZE = std::extent<decltype(B)>::value; 

// A and B must be the same size 
assert(ASIZE == BSIZE); 

// p = sorted permutation of B largest to smallest 
std::vector<size_t> p(ASIZE); 
std::iota(p.begin(), p.end(), 0); 
std::sort(p.begin(), p.end(), [&](size_t i1, size_t i2) { return B[i1] > B[i2]; }); 

// pinv = inverse of p 
std::vector<size_t> pinv(ASIZE); 
for (size_t i = 0; i < ASIZE; ++i) 
    pinv[p[i]] = i; 

// Sort A largest to smallest 
std::sort(std::begin(A), std::end(A), [&](int v1, int v2) { return v1 > v2; }); 

次に、あなたはpinv通じた間接あなたが望む順番でAを取得することができます。

for (size_t index : pinv) 
    std::cout << A[index] << " "; 
std::cout << std::endl; 
// Output is: 20 16 8 9 14 11 

Answer 2

これはコピー操作であり、並べ替えではないようです。

第2の配列は、の配列番号を示しています。違いは、2番目の配列から1を引いて、ソートされた配列のオフセットを得ることです。

const int original_array[]={8, 9, 11, 14, 16, 20}; 
const int ordering_array[]={6, 5, 1, 2, 4, 3}; 
int result array[6]; 
for (unsigned int i = 0; 
    i < sizeof(original_array)/sizeof(original_array[0]); 
    ++i) 
{ 
    int source_index = ordering_array[i] - 1; 
    result_array[i] = original_array[source_index]; 
} 

Answer 3

あなたの最初の例から、あなたがインデックスBの配列を使用してAを置換するために望んでいたように見えました。しかし、2番目の例では、並べ替えが実際に必要だが、Aの値ではなく、Bの値に基づいた比較を示しています。

あなたが必要とするのは、「ソートキー機能」をとるソート機能です。ソートキー関数には、配列インデックスを引数として渡す必要があります。

Cのqsortキー機能がかかりますが、鍵関数の引数は、を比較される値のインデックスは、を比較さ値ではありません。それはあなたのために働くことはありません。

おそらくあなた自身のソート機能を記述する必要があります。それは厳しくない。配列が小さい場合には、簡単な挿入ソートがうまく行います。

void sort_by_keys(int *values, int *sortkeys, int size) 
{ 
    int i, j; 

    for (i = 1; i < size; i++) { 
    j = i; 

    /* For a usual insertion sort, the condition here 
     * would be values[j] < values[j-1]. */ 
    while (j > 0 && sortkeys[j] < sortkeys[j-1]) { 
     swap(values, j, j - 1); 
     swap(sortkeys, j, j - 1); 
     j--; 
    } 
    } 
} 

を（あなたはswapあなた自身を記述する必要があります。）

配列が大きい場合は、自分自身をコーディングすることができます再帰的または反復的なクイックソート。どちらも難しいことではありません。テストケースを作成して確実に動作させるようにしてください。テストケースに空の配列と1つの項目を含む配列を含める必要があります。