# How to sort a Vec by another Vec?

I have two `Vec`s:

``````let original_vec = vec!["a", "b", "c", "d", "e"];
let index_vec = vec![2usize, 0, 4, 3, 1];
``````

I need sort the `original_vec` by `index_vec` based on the eliments of `index_vec`. The `index_vec` is `2`, which imply that `original`(that is `"a"`) should be located at `2` position. Then the expected sorted result should be this:

``````vec!["b", "e", "a", "d", "c"]
``````

What should I do to get that?

1 Like

An easy solution would be to create a new vec using those indices.

``````fn sort<T: Clone>(original: &[T], indices: &[usize]) -> Vec<T> {
let mut sorted = Vec::new();

for &index in indices {
sorted.push(original[index].clone());
}

sorted
}
``````

(playground)

This clones each element, but for something like a `&str` that'll be a no-op.

2 Likes

Yes, the method will clones each element. If the elements of `original_vec` is expensive to clone, and I must avoid to clone it, what should I do?

Here's an in-place version of the algorithm, but it modifies the index list as well:

``````fn place_at_indices<T>(original: &mut [T], indices: &mut [usize]) {
for i in 0..indices.len() {
while i != indices[i] {
let new_i = indices[i];
indices.swap(i, new_i);
original.swap(i, new_i);
}
}
}
``````

Playground

If you don't want the list of indexes to be modified, clone it first. If the list doesn't include exactly one of each index, then this will run into an infinite loop.

5 Likes

Itertools::sorted_by_key

Rust Playground

For expensive key functions (e.g. functions that are not simple property accesses or basic operations), use `sorted_by_cached_key`

2 Likes

An alternative is to go through another data structure, like a `BTreeMap`:

``````fn reorder<T>(orig: Vec<T>, idx: &[usize])->Vec<T>{
assert_eq!(orig.len(), idx.len());
let n = orig.len();
let mut idx_map = idx.into_iter()
.zip(orig)
.collect::<BTreeMap<_,_>>();

(0..n).map(|i| match idx_map.remove(&i) {
Some(x) => x,
None => panic!("No item at index {i}!")
}).collect()
}
``````
1 Like

This doesn't seem to require anything but `zip` and `sort_by_key()`: Playground

``````let items = vec!["a", "b", "c", "d", "e"];
let keys = vec![2usize, 0, 4, 3, 1];

let mut tmp: Vec<_> = items
.into_iter()
.zip(keys)
.collect();

tmp.sort_by_key(|&(_, key)| key);
``````

Note that OP doesn't want to have `element[index[i]]` at position `i`! That is different from sorting the elements by the corresponding numbers (it's a slightly harder problem).

5 Likes

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.