Sorting array of pointers

[samuelpilz]

I have data stored spread out (x and y in the example below) and I want to sort them relative to each other.
Is this somehow possible with the stdlib or do I need to write my own sorting algorithm?

fn sort_references<T: Ord>(arr: &mut [&mut T]) {
    todo!();
    // sort by writing to the underlying data, not swap pointers in array
}

#[test]
fn tests() {
    let mut x = 2;
    let mut y = 1;
    sort_references(&mut [&mut x, &mut y]);
    assert_eq!(x, 1);
    assert_eq!(y, 2);
}

• T is not necessarily Clone
• The arrays are quite small (<50 elements) but dynamic in size

[quinedot]

I think you'll need your own. ^[1]

Incidentally by sorting the objects directly in the slice, the std implementation can move ranges of elements all at once with a memcpy. You would need reads and writes for each element.

So the ideal algorithm is probably different anyway.

---

1. Alternatively you could sort some wrapper that remembers source index and then figure out how to swap things around afterwards, but that doesn't seem any nicer to me. ↩︎

[samuelpilz]

I read the internal code a bit and saw this: rust/sort.rs at bbdca4c28fd9b57212cb3316ff4ffb1529affcbe · rust-lang/rust · GitHub
Blocking seems quite smart here.

Wrapper with index seems reasonable for my use case, although the swaping might not be a trivial algorithm as well (probably chase cycles)

[quinedot]

Yeah, it's "keep track of unseen indices and chase cycles" or so.

Naive (but no unsafe) version.

[ambiso]

@quinedot

Naive (but no unsafe) version.

Very cool!
Small suggestion: using Vec<bool> or bit_vec should save some hashing and HashSet growing operations.

Like this.

[ambiso]

Incorporating the ideas from sorting - How to sort a vector by indices in Rust - Stack Overflow

and fore-going the 2nd extra allocation for the permutation we obtain this:

Rust Playground

[tczajka]

It almost seems just as easy to implement a sorting algorithm from scratch. Here is heap-sort:

Rust Playground