How to sort a vector by indices in Rust

user_5299417 0
Viewed 1024

I want to sort (reorder) a vector (inplace) by a predefined ordering in Rust.

For example

let i = vec![0, 3, 2, 1];
let mut v = vec!["a", "b", "c", "d"];
v.sort_by_indices(&i);

assert_eq!(v, &["a", "d", "c", "b"]);

I would like to do this inplace. In my use case, v takes up a lot of memory.

Note: this question is a natural follow-on from How to get the indices that would sort a vector in Rust?

rust sorting
3 Answers

An in-place implementation is tricky but possible in O(n) time. It works by chasing indices and swapping elements until it gets back to where it started. Unfortunately, this does require scratch space to keep track of what elements are already sorted. Here's an implementation that reuses the index array if its allowed to consume it:

fn sort_by_indices<T>(data: &mut [T], mut indices: Vec<usize>) {
    for idx in 0..data.len() {
        if indices[idx] != idx {
            let mut current_idx = idx;
            loop {
                let target_idx = indices[current_idx];
                indices[current_idx] = current_idx;
                if indices[target_idx] == target_idx {
                    break;
                }
                data.swap(current_idx, target_idx);
                current_idx = target_idx;
            }
        }
    }
}

See it working on the playground (with improvements by @Jmb).

Otherwise you would need a separate allocation for the scratch space (perhaps a BitVec). Feel free to comment or edit if this method is possible without keeping track of the sorted elements.

user_21891300

In the same way it enough to implement yourself

let i = vec![0, 3, 2, 1];
let mut v = vec!["a", "b", "c", "d"];

v = i.into_iter().map(|x| v[x]).collect::<Vec<&str>>();

assert_eq!(v, &["a", "d", "c", "b"]);
user_119980290

You can create a HashMap or BTreeMap lookup table and use it as key searcher:

use std::collections::HashMap;
fn main() {
    let i = vec![0, 3, 2, 1];
    let mut v = vec!["a", "b", "c", "d"];

    let keys: HashMap<_, _> = v.iter().cloned().zip(i.iter()).collect();
    v.sort_by_cached_key(|e| keys[e]);

    assert_eq!(v, &["a", "d", "c", "b"]);
}

Playground

user_16951720
Related