Сортировка массива в соответствии с последовательностью другого массива

Question

Предположим, у меня есть массив A[]={8, 9, 11, 14, 16, 20};, который я должен сортировать по другому массиву B[]={6, 5, 1, 2, 4, 3};.

Сортировано A будет A[]={20, 16, 8, 9, 14, 11};

Итак, как A будет отсортирован сказано в B.
Первый элемент B является самым большим, поэтому первый элемент A также будет самым большим. Третий элемент B является самым маленьким, так третий элемент A также будет наименьшее

Если B было что-то отсортированные нисходящее как {100, 84, 74, 51, 5, 1} Тогда A также будут рассортированы по убыванию.
Примеры:
1. если B = {12, 8, 14, 156, 2, 84}, A было бы {11, 9, 14, 20, 8, 16}
2. если B = {2, 3, 45, 0, 7, 56}, A будет {9, 11, 16, 8, 14, 20}

его, как если у меня есть несколько друзей разных возрастов, и я хочу, чтобы дать им что-то по до их возраста. Самый старший человек получит самый большой ... меньше, чем он получит меньший, чем тот ... и так далее.

Я видел похожие вопросы, но они не похожи на мою проблему.
Моя идея - сортировать как первые. А потом перестройте.

Есть ли быстрое решение?

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

Похоже, что это операция копирования, а не сортировка.

Второй массив показывает заказ элементов первого массива. Разница заключается в вычитании 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

С первого примера, оказалось, что вы хотели переставить A с использованием массива индексов B. Но второй пример показывает, что вы действительно хотите сортировку, но с сравнениями, основанными на значениях в B, а не в A.

Так что вам нужна функция сортировки, которая принимает «функцию сортировки ключей». Ключевой функцией сортировки должен быть передан индекс массива в качестве аргумента.

Кассиопеяне 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.)

Если массивы больше, вы можете закодировать себя вверх рекурсивный или итеративный quicksort. Это тоже не сложно.Убедитесь, что вы также пишете несколько тестовых примеров, чтобы убедиться, что они работают. Ваши тестовые примеры должны включать пустые массивы и массивы с 1 элементом.