🦀

Rustのソートの理屈を大雑把に理解する

に公開
Rust
tech

概要

備忘録も兼ねて、Rustのソートを調べた時の記録を残しておきます。

基本型のベクタを昇順ソートするだけならsort()メソッドで事足りますが、少し複雑なことをしようとすると自前でソートのロジックを定義する必要があります。
あくまで大まかな理解のために必要な最低限の事柄のみに絞ります。

自前のロジックを定義する方法

比較関数の書き方

ソートのロジックを定義するには、sort_by()といったソート用メソッドにクロージャーとして比較関数を渡します。
ソートに使用するメソッドは他にもいろいろありますが割愛。

例：構造体のベクタを特定のフィールドでソート

#[derive(Debug)]
struct Person {
    name: String,
    age: i32,
}

let mut people = vec![
    Person{name: String::from("taro"), age: 28},
    Person{name: String::from("jiro"), age: 14},
    Person{name: String::from("hanako"), age: 28},
];

people.sort_by(|a, b| a.name.cmp(&b.name));
println!("{:?}", people); // [Person { name: "hanako", age: 28 }, Person { name: "jiro", age: 14 }, Person { name: "taro", age: 28 }]

比較関数にでてきたcmp()メソッドは以下のようにOrdering型のenumを返します。

  • a < b ならば Ordering::Less
  • a = b ならば Ordering::Equal
  • a > b ならば Ordering::Greater

では、Orderingとは？

Ordering

std::cmp::Ordering

Orderingは2つの値の比較結果を表現しており、次のように定義されています。

pub enum Ordering {
    Less = -1,
    Equal = 0,
    Greater = 1,
}

sort_by()メソッドは比較関数の引数a, bに対し返ってくる値に応じて要素の大小関係を把握し、ソートを実行します。

  • Less ならば aがbより前に位置する
  • Greater ならば aがbより後に位置する
  • Equal ならば元の順番を維持（ただし、これはsort_by()が安定ソートであるためで、不安定ソートを実行するメソッドでは保証されないと考えられます）

実例

理解を深めるためにいくつかの例に当たってみます。

降順ソート

reverse()メソッドは以下のようにOrderingを変換するため、順番が逆になり降順でソートできます。

  • Less -> Greater
  • Greater -> Less
  • Equal -> Equal 
let mut numbers = vec![1, 5, 3, 2];
// 降順ソート
numbers.sort_by(|a, b| a.cmp(&b).reverse());
println!("{:?}", numbers); // [5, 3, 2, 1]

もちろんreverse()を使わずとも次のように実装することもできます。

numbers.sort_by(|a, b| b.cmp(&a));

複数キーでソート

then()によってOrderingをつなげることができます。

let mut people = vec![
    Person{name: String::from("taro"), age: 28},
    Person{name: String::from("jiro"), age: 14},
    Person{name: String::from("hanako"), age: 28},
];
people.sort_by(|a, b| a.age.cmp(&b.age).then(a.name.cmp(&b.name)));
println!("{:?}", people); // [Person { name: "jiro", age: 14 }, Person { name: "hanako", age: 28 }, Person { name: "taro", age: 28 }]

この例ではage > nameの優先順位でソートしています。すなわち、ageが同じ人達の中での並び順はnameの辞書順となっています。

Ordering型であるo1とo2に対しo1.then(&o2)のようにthen()を呼んだ時、then()は

  • o1がEqual以外（LessまたはGreater） ならば o1を返す
  • o1がEqual ならば o2を返す

という働きをします。

すなわち、上の例においては

  • a.age.cmp(&b.age)がEqualでない場合（ageが異なる場合）-> 比較関数はa.age.cmp(&b.age)の結果を返す（ageの比較結果を元に順番を決める）
  • a.age.cmp(&b.age)がEqualの場合（ageが等しい場合）-> 比較関数はa.name.cmp(&b.name)の結果を返す（nameの比較結果を元に順番を決める）

となります。そのため、age、nameという2つのキーを用いてソートすることができるのです。

まとめ

Orderingの働きがわかればいろいろ応用が効きそうです。

Discussion