CODEWITHSUNDEEP
sortingrust
Michael Hall
Michael Hall

Reputation: 3330

How to sort (reorder) a Vec by indices?

I want to sort (reorder) a Vec in-place 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 in-place. In my use case, v takes up a lot of memory.

This question is a follow-up to How to get the indices that would sort a Vec?

Upvotes: 6

Views: 2800

Answers (3)

kmdreko
kmdreko

Reputation: 59882

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.

Upvotes: 8

Netwave
Netwave

Reputation: 42678

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

Upvotes: 1

Zeppi
Zeppi

Reputation: 1235

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"]);

Upvotes: 1

Related Questions