Сортировка массива C на основе содержимого другого массива

Question

Я пытаюсь отсортировать массив A, элементы которого являются индексами.Индексы ссылаются на другой массив B, значение которого будет определять порядок A.Итак, я бы хотел отсортировать A так, чтобы B[ A[i] ] увеличивалось.

Например:

A = [0, 1, 4, 5, 7]
B = [5, 3, 8, 2, 2, 7, 1, 6, 3, 9]

Сортировка A будет

A' = [ 7, 4, 1, 0, 5 ]

Возможно ли это со встроенной сортировкой C, или мне придетсянаписать мою собственную реализацию?

РЕДАКТИРОВАТЬ: Эти массивы являются локальными переменными функции.

Answer 1

Если вы хотите использовать qsort, лучшее, что нужно сделать, - это переупорядочить индексы в A и значения в B в структуру, а затем создать компаратор на основе нового массива, который структурирует.Например:

typedef struct
{
    int index_from_A;
    int value_from_B;
} index_value_wrapper;

index_value_wrapper index_wrapper_array[5];

for (int i=0; i < 5; i++)
{
    index_wrapper_array[i].index_from_A = A[i];
    index_wrapper_array[i].value_from_B = B[A[i]];
}

int comparitor (const void* lhs, const void* rhs)
{
    return (lhs.value_from_B - rhs.value_from_B);
}

Теперь вы можете запустить qsort для массива struct и оттуда вы можете извлечь правильную отсортированную последовательность, которую вы хотели для исходного массива A, без необходимости использовать пользовательскую функцию сортировки.

Answer 2

Если он у вас есть, qsort_r предоставляет способ сделать это. Вы можете дать ему контекстную информацию в дополнительном параметре. Этот контекст передается в функцию сравнения. Вы можете получить доступ к этой дополнительной информации для извлечения желаемой информации сортировки.

Компилятор Microsoft имеет аналогичный: qsort_s

Answer 3

Я думаю, вы можете использовать qsort и пользовательский компаратор

int comparator(const void *x, const void *y)
{
    return ( b[*(int*)x] - b[*(int*)y] );
}

Answer 4

Создайте еще один массив C типа struct { int a_value; int b_value}, инициализируйте каждый элемент значениями каждого индекса a и значения, найденного из b.Отсортируйте это, просмотрите отсортированный C, копируя a_values ​​обратно в A.

Viola.Нет, это большая скрипка.Voila!

Answer 5

Используйте ваше правило в качестве функции сравнения для qsort (если B длиннее, чем A):

#include <stdio.h>
#include <stdlib.h>

int A[] = {0, 1, 4, 5, 7};
int B[]= {5, 3, 8, 2, 2, 7, 1, 6, 3, 9};

 int my_cmp(const void *a_, const void *b_,void *arg_)
 {
   const int *a = a_, *b = b_;

   if(B[*a] == B[*b])
       return 0;
    else if (B[*a] < B[*b])
        return -1;
    else
        return 1;

}

int main(int argc,char *arga[])
{
    int i;

    qsort(A,sizeof A/sizeof A[0] ,sizeof A[0],my_cmp);

    puts("Sorted A");
    for(i = 0 ; i < sizeof A/sizeof A[0]; i++) {
        printf("A[%d] : %d B[A[%d]] : %d\n",i,A[i],i,B[A[i]]);
    }

    return 0;
}

Это дает:

$ ./a.out
Sorted A
A[0] : 4 B[A[0]] : 2
A[1] : 1 B[A[1]] : 3
A[2] : 0 B[A[2]] : 5
A[3] : 7 B[A[3]] : 6
A[4] : 5 B[A[4]] : 7

Доступно на многих платформах также qsort_r (в linux вам нужно будет #define _GNU_SOURCE, прежде чем включать <stdlib.h>, чтобы использовать его. Используя это, вы измените функцию сравнения, например,

int my_cmp(const void *a_, const void *b_,void *arg_)
 {
    const int *a = a_, *b = b_, *arg = arg_;

   if(arg[*a] == arg[*b])
       return 0;
    else if (arg[*a] < arg[*b])
        return -1;
    else
        return 1;

}

И вызвать qsort_r как

qsort_r(A,sizeof A/sizeof A[0] ,sizeof A[0],my_cmp,B);