Types of arrays and their position

Question

I have a sorting problem.

I have two arrays

int a[] ={index1,index2,index3...indexI}; int b[] ={num1,num2,num3.......numI}; 

Array b [] has numbers in random order, but their position corresponds to the position in []. For example, num1 is the value of index1, num2 is the value of index2.

The problem is this:

I need to sort the elements of b [] in descending order, at the same time I need to move the position of the elements [] according to the sorted order of b [].

I can sort b [] in descending order using one of the sorting algorithms, but I cannot handle the simultaneous movement of elements [] according to the change in position b []. My end result that I expect is the indices [], ordered in descending order of their values ​​in b [].

Please, help.

thanks

Answer 1

If I get it right, I want to have something like this = [0 1 2]; b = [5 2 8] and after sorting a = [1 0 2]; b = [2 5 8].

Which of the sorting algorithms should you just remember about changing index arrays when changing the position of a number:

eg. replacing two positions (pseudo-code)

 swap(i, j): // i, j - indexes (b[i], b[j]) = (b[j], b[i]) // swap values (a[i], a[j]) = (a[j], a[i]) // swap the indexes 

Answer 2

 int a[] ={index1,index2,index3...indexI}; int b[] ={num1,num2,num3.......numI}; int c[] = {{num1, index1}, {num2, index2}...{indexI, numI}} sort(c); for i = 0 to c.len print c[i][1] 

In C ++, I would use a vector of pairs. In other languages ​​you can use structure.

Answer 3

After sorting b you can sort a using a comparison function that looks for values ​​in b .

 // assuming b is visible at the module level, you can pass this to qsort int compare_by_indexing_into_b(void const *a, void const *b) { int i = *(int const *)a; int j = *(int const *)b; return b[i] - b[j]; } 

Answer 4

You can do this in two ways: first, sort a using your favorite sorting algorithm, but instead of comparing a[i] with a[j] directly compare b[a[i]] with b[a[j]] . Now rebuild b according to the indices in a - and you are done.

The second step may look like this (in pseudocode):

 var c = new int[b.length] for (int i = 0 ; i != a.length ; i++) c[i] = b[a[i]] b = c 

Answer 5

This shows one of the drawbacks of using parallel arrays instead of the struct array. A simple solution would be to convert your code to use

  struct {int index, num;} a[] = {{index1, num1},{index2, num2}, ...}; 

If your code base already makes heavy use of parallel arrays, you can write a view that knows about such difficulties. You can give it an array of arrays, not just one, and write a sort to perform swaps on each array, but only perform comparisons on the first. In other words:

 void sort_pa(void **arrays/*NULL-terminated*/, int len,int size, int(*cmp)(...))) 

which you then used:

 int a[] ={index1,index2,index3...indexI}; int b[] ={num1,num2,num3.......numI}; int *c[] = {b, a, NULL}; sort_pa(c, I, sizeof **c, cmp); 

Answer 6

Using qsort, you will sort the array a using the following comparison expression:

 b[*(int*)elem1] - b[*(int*)elem2] 

where elem1 and elem2 are two pointer arguments for the comparator function (let b be a visible function).

This will leave the array b untouched, and b [a [i]] will give the b elements in descending order.