3

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?

Improve this question
12
  • 1
    Exactly this question has been here a few days, maybe a week, ago. Except for your array literals don't give a hint how exactly B specifies the sorting order of A. Check them please. Commented May 15, 2016 at 18:53
  • I have no idea how B determines the order of A, please clarify your sorting criteria. Commented May 15, 2016 at 18:56
  • A 6 in B means the sixth element of A should be where the 6 is located. The 6 is at the beginning, so the sixth element of A should move to the beginning. Commented May 15, 2016 at 18:58
  • Is values in ur array B are actually showing indexes to sort array A ? If so than it is very simple you just have to swap ur array members based on values and index of array B. Commented May 15, 2016 at 19:09
  • first element of B is the greatest.. so first element of A will also be the greatest, third element of B is the smallest so third element of A will also be the smallest.... Commented May 16, 2016 at 3:39

3 Answers 3

Reset to default
4

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Shell sort shares this simplicity while being much more efficient - which makes it more recommended for this problem.
@plasmacel, if I wanted to be pedantic, I would say that it depends on the size of the arrays. (Insertion sort is very hard to beat on small arrays.) But it's not worth debating. Shell sort would also be fine.
3

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];
}
Improve this answer

1 Comment

Well, B can also be like this B={102, 94, 4, 17, 87, 54}
2

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
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.