1
\$\begingroup\$

I am learning sorting in rust. I want to sort vector as such that even numbers go first

My code is OK. But can it be improved (I want to use sort function)?

fn main() {
    let mut v = vec![1, 2, 10, 4, 3];
    v.sort_by(|a, b | {
        (a % 2).cmp(&(b % 2))
    });
    println!("{:?}", v); // [1, 2, 10, 4, 3]

}
 
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Looks good to me. But that's an odd comparison function, which discards all the high-order bits. You're sure you wouldn't care to use magnitude as a tie breaker? I mean, you have the first half of a bucket sort, assigning to one of two buckets. But the "sort within bucket" part is missing. \$\endgroup\$
    – J_H
    Apr 24, 2023 at 22:49
  • 4
    \$\begingroup\$ v.sort_by_key(|v| v % 2) \$\endgroup\$ Apr 25, 2023 at 18:30

2 Answers 2

4
\$\begingroup\$

Partition the Array

This is the standard example of std::iter::Iterator::partition. There is also a nightly experimental partition_in_place.

let (even, odd): (Vec<_>, Vec<_>) = a
    .into_iter()
    .partition(|n| n % 2 == 0);

This runs in O(N) time, while sorting takes O(N log N) time.

If you want the even and odd collections to be sorted (which this doesn’t do), it’s more efficient to partition and then sort the sub-arrays. Sorting has worse-than-linear time complexity, so it’s better to sort two partitions than one large array.

\$\endgroup\$
1
\$\begingroup\$

x % 2 has a nasty pitfall

And it results in a bug this time.

How much is -1 % 2? It couldn't be 0 of course, but it's also not 1. Not in Rust anyway, it does vary by language.

With this data: let mut v = vec![1, 2, 10, 4, 3, -1, -2, -3];, I get this result:

[-1, -3, 2, 10, 4, -2, 1, 3]

Probably not what you want.

On the other hand, x & 1 properly results in 0 for even numbers and 1 for odd numbers, positive or negative.

Using x % 2 to decide even/odd is not always wrong. If the result is compared to zero, it doesn't matter that odd numbers sometimes result in +1 and sometimes in -1, either way the result isn't zero. That's why Davislors answer doesn't suffer from this bug, despite using n % 2.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Or x.rem_euclid(2). \$\endgroup\$
    – L. F.
    May 2, 2023 at 17:33
  • \$\begingroup\$ Rustc with release flags optimizes n%2 == 0, into a bitwise and, automatically. So, yes, they’re equivalent. \$\endgroup\$
    – Davislor
    May 2, 2023 at 23:39
  • \$\begingroup\$ Also, like I said in my answer, that’s not my code. It’s an example from the Rust standard library documentation I linked to. \$\endgroup\$
    – Davislor
    May 2, 2023 at 23:40
  • \$\begingroup\$ But, flattered that you’d give me credit for it! \$\endgroup\$
    – Davislor
    May 2, 2023 at 23:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.