CODEWITHSUNDEEP
c++arrayssorting
Symon Saroar
Symon Saroar

Reputation: 67

Sort an array according to the sequence of another array

Suppose I have an Array A[]={8, 9, 11, 14, 16, 20}; which I have to sort according to another array B[]={6, 5, 1, 2, 4, 3};.

Sorted A would be A[]={20, 16, 8, 9, 14, 11};

So, How A will be sorted is told in B.
First element of B is the greatest so first element of A will also be the greatest. Third element of B is smallest so third element of A will also be the smallest

If B were something sorted Descending like {100, 84, 74, 51, 5, 1} Then A will also be sorted Descending.
Examples:
1. if B = {12, 8, 14, 156, 2, 84}, A would be {11, 9, 14, 20, 8, 16}
2. if B = {2, 3, 45, 0, 7, 56}, A would be {9, 11, 16, 8, 14, 20}

Its like if I have some friends of different ages, and I want to give them something according to their ages. Eldest person will get the biggest one... smaller than him will get the smaller one than that.. and so on.

I have seen similar questions but they are not like my problem.
My idea is to sort both first. And then rearrange.

Is there any fast solution?

Upvotes: 3

Views: 2305

Answers (3)

clstrfsck
clstrfsck

Reputation: 14847

If I understand your question correctly, you want to calculate the inverse of the sorted permutation of B, and then order sorted A in that order. You can do this pretty easily with the standard library.

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

Then you can indirect through pinv to get A in the order you want.

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

Upvotes: 2

Alex D
Alex D

Reputation: 30465

From your first example, it appeared that you wanted to permute A using an array of indices B. But the second example shows that you actually do want a sort, but with comparisons based on the values in B rather than those in A.

So what you need is a sort function which takes a "sort key function". The sort key function should be passed an array index as an argument.

C's qsort does take a key function, but the arguments to the key function are the values being compared, not the indices of the values being compared. So it won't work for you.

You'll probably have to write your own sort function. It's not hard. If the arrays are small, a simple insertion sort will do just fine:

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

(You'll have to write your own swap.)

If the arrays are larger, you can code yourself up a recursive or iterative quicksort. It's not hard either. Make sure you also write some test cases to ensure it works. Your test cases should include empty arrays and arrays with 1 item.

Upvotes: 4

Thomas Matthews
Thomas Matthews

Reputation: 57749

Looks like this is a copy operation and not a sort.

The second array shows the ordering of the elements of the first array. The difference is to subtract 1 from the second array to get the offset of the sorted array.

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

Upvotes: 3

Related Questions