How to sort a Vec by another Vec?

[Bria]

I have two Vecs:

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[0] is 2, which imply that original[0](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?

[Michael-F-Bryan]

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.

[Bria]

Thanks for your reply.
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?

[marcianx]

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.

[vague]

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

[2e71828]

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

Rust Playground

[H2CO3]

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).