Ein Array nach der Reihenfolge eines anderen Arrays sortieren

Question

Angenommen, ich habe ein Array A[]={8, 9, 11, 14, 16, 20};, das ich nach einem anderen Array B[]={6, 5, 1, 2, 4, 3}; sortieren muss.

Sorted AA[]={20, 16, 8, 9, 14, 11};

So wäre Wie A sortiert werden in B erzählt.
Erstes Element von B ist das größte, also erstes Element von A wird auch das größte sein. Drittes Element von B kleinstem ist so drittes Element A auch die kleinsten wird

Wenn B so etwas wie {100, 84, 74, 51, 5, 1} Absteigen sortiert waren Dann A auch absteigend sortiert werden. Beispiele
:
1. wenn B = {12, 8, 14, 156, 2, 84}, A{11, 9, 14, 20, 8, 16}
2. wenn B = {2, 3, 45, 0, 7, 56} wäre, A{9, 11, 16, 8, 14, 20}

Sein sein würde, wenn ich ein paar Freunde haben unterschiedlichen Alters, und ich möchte ihnen etwas geben nach zu ihren Altern. Älteste Person wird die größte bekommen ... kleiner als er wird die kleinere bekommen ... und so weiter.

Ich habe ähnliche Fragen gesehen, aber sie sind nicht wie mein Problem.
Meine Idee ist, beide zuerst zu sortieren. Und dann neu anordnen.

Gibt es eine schnelle Lösung?

Answer 1

Wenn ich Ihre Frage richtig verstanden habe, möchten Sie die Umkehrung der sortierten Permutation von B berechnen und dann sortierte A in dieser Reihenfolge sortieren. Sie können dies mit der Standardbibliothek ziemlich einfach tun.

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

Dann können Sie indirekt durch pinvA in der Reihenfolge, die Sie wollen.

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

Answer 2

Sieht aus wie das ist ein Kopiervorgang und nicht eine Art.

Das zweite Array zeigt die Bestellung der Elemente des ersten Arrays. Der Unterschied besteht darin, 1 von dem zweiten Array zu subtrahieren, um den Offset des sortierten Arrays zu erhalten.

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

Von Ihrem ersten Beispiel erschien es, dass Sie A unter Verwendung einer Anordnung von Indizes B permutieren wollte. Aber das zweite Beispiel zeigt, dass Sie tatsächlich eine Sortierung wünschen, aber mit Vergleichen basierend auf den Werten in B und nicht in A.

Was Sie brauchen, ist eine Sortierfunktion, die eine "Sortierschlüsselfunktion" benötigt. Der Sortierschlüsselfunktion sollte ein Array-Index als Argument übergeben werden.

C des qsort hat eine Schlüsselfunktion übernehmen, aber die Argumente der Schlüsselfunktion sind die Werte verglichen werden, nicht die Indizes der Werte verglichen werden. Also wird es nicht für dich funktionieren.

Sie müssen wahrscheinlich Ihre eigene Sortierfunktion schreiben. Es ist nicht schwer. Wenn die Arrays klein sind, ein einfaches Einsetzen Art wird gut tun:

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

(Sie müssen werden Ihr eigenes swap schreiben.)

Wenn die Arrays größer sind, können Sie sich Code auf ein rekursiver oder iterativer Quicksort. Es ist auch nicht schwer.Stellen Sie sicher, dass Sie auch einige Testfälle schreiben, um sicherzustellen, dass es funktioniert. Ihre Testfälle sollten leere Arrays und Arrays mit 1 Element enthalten.