Sorting a slice with external keys

1

Lets say I have two slices a and b of same size. I would like to sort a with keys contained in b.
Is there an easy way to achieve this ?

What I've tried:

  • using sort_by_key: it could be easy if the index of the element was passed to the extraction function, then i would just need to index b with that same index, unfortunately it takes a reference to the element itself.
  • by zipping:
let mut zipped = a.into_iter().zip(b).collect::<Vec<_>>();
zipped.as_mut_slice().sort_by_key(|(_a, b)| *b);
let (sorted_a, sorted_b): (Vec<_>, Vec<_>) = zipped.into_iter().unzip();

Unfortunately this is very cumbersome and requires to copy the two arrays.
I wish there was a function sort_by_index_key where the extraction key would take the index of the current value as its argument to be able to achieve this.

2 Likes
2

Just a note, because Vec inplements Deref, you don't have to call as_mut_slice.

3

It's tough. The ideal method for this is missing indeed.

Index from ref

However, you can translate a reference to an index.

The method is unstable, but you can just copy it to use it on stable: https://doc.rust-lang.org/src/core/ptr.rs.html#1239-1245

Oh wait, that won't work. Because the elements get swapped, so the indices become useless when sorting progresses.

Your version can be done with a little less copying. You can make a temp array of just the indices (0...a.len()).collect()), sort them, and then make the new a from the indices.

2 Likes
4

Oh I see. It would require to sort b at the same time so that the indices stay valid throughout the sorting process.

Anyway I'll go for the temp array solution, thanks!

5

https://stackoverflow.com/q/32564455/155423

The answer there suggests using permutation.

2 Likes