🦀

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

2024/03/15に公開

概要

備忘録も兼ねて、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 ならば abより前に位置する
  • Greater ならば abより後に位置する
  • 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型であるo1o2に対しo1.then(&o2)のようにthen()を呼んだ時、then()

  • o1Equal以外(LessまたはGreater) ならば o1を返す
  • o1Equal ならば 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の比較結果を元に順番を決める)

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

まとめ

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

Discussion