Sorting a C array based on contents of another array

I'm trying to sort an array A whose elements are indexes. The indexes refer to another array B whose value will determine the order of A. So, I would like to sort A such that B[ A[i] ] is increasing.

For example:

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

Sorted A would be

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

Is开发者_如何学C this possible with C's built-in sort, or am I going to have to write my own implementation?

EDIT: These arrays are local function variables.

If you want to use qsort, the best thing to-do would be to re-wrap the indexes in A and the values in B into a struct, and then make a comparator based on a new array that struct. For instance:

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

Now you can run qsort on the struct array and from there you can extract the proper sorted sequence you desired for the original array A without having to use a custom sorting function.

If you have it available, qsort_r provides a way to do this. You can give it context information in an additional parameter. That context is passed to the comparison function. You can access that additional information to extract the desired sorting information.

The Microsoft compiler has a similar one: qsort_s

I think you can use qsort and a custom comparator

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

Create another array C of type struct { int a_value; int b_value}, initialise each element to the values of each index of a and the value looked up from b. Sort that, traverse the sorted C copying the a_values back into A.

Viola. No, that's a large violin. Voila!

Use your rule as the comparison function to qsort (as long as B is longer than 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;
}

This gives:

$ ./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

Available on many platforms is also qsort_r(on linux you'll have to #define _GNU_SOURCE before including <stdlib.h> to use it. Using that, you'd change the comparison function to e.g.

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;

}

And call qsort_r like

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