Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Sorting a C array based on contents of another array

Tags:

arrays

c

sorting

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

like image 255
ajwood Avatar asked May 20 '11 19:05

ajwood


People also ask

How do you sort an array based on another array?

Method 1 (Using Sorting and Binary Search)Create a temporary array temp of size m and copy the contents of A1[] to it. Create another array visited[] and initialize all entries in it as false. visited[] is used to mark those elements in temp[] which are copied to A1[]. Initialize the output index ind as 0.

How do I sort two arrays simultaneously?

Solution without object overheadMake a third array. Fill it with indices from 0 to size-1 . Sort this array with comparator function polling into the array according to which you want to sort. Finally, reorder the elements in both arrays according to indices.

How do you sort an array in a specific order?

Sorting an array of objects in javascript is simple enough using the default sort() function for all arrays: const arr = [ { name: "Nina" }, { name: "Andre" }, { name: "Graham" } ]; const sortedArr = arr.

What is relative order array?

The relative order of the elements is simply the order that the elements within a particular partition have with respect to each other. For example, after partition ing {1,7,3,10,9,6}


1 Answers

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.

like image 156
Jason Avatar answered Sep 23 '22 23:09

Jason