Rustの並べ替えと検索

並べ替え（ソート）と検索は、ほとんどどんなプログラムにも出てくる作業です。点数順にプレイヤーを並べる、名前順にファイルを表示する、いちばん安い商品を探す、などなど。Rustのベクタとスライスには、どちらの作業にも使える組み込みのメソッドがそろっているので、自分でアルゴリズムを書く必要はほとんどありません。

これらのメソッドの多くは、2つの要素をどう比べるかを表すクロージャを受け取ります。この考え方ひとつに慣れてしまえば、このページの残りはそのバリエーションにすぎません。

sortとsort_unstable

.sort() は要素を昇順（小さい順）に並べます。ベクタをその場で（in place）書き換えるので、ベクタは mut でなければなりません。数値は値の大きさで、文字列はアルファベット順で並びます。

fn main() {
    let mut scores = vec![42, 7, 99, 7, 15];
    scores.sort();
    println!("{:?}", scores);

    let mut names = vec!["Zoe", "adam", "Bob", "Ana"];
    names.sort_unstable();
    println!("{:?}", names);
}

実行結果:

[7, 7, 15, 42, 99]
["Ana", "Bob", "Zoe", "adam"]

▶ 実際に試してみよう

注目してほしい点が2つあります。

• "adam" が最後に来ています。文字列は文字コードで比べられ、大文字はすべて小文字より前に来るからです。辞書のような順番にしたいなら、name.to_lowercase() で並べ替えます（このあと紹介します）。名前を英語のままにしているのも、この大文字・小文字の違いを見てもらうためです。
• sort_unstable はたいてい少しだけ速く、余分なメモリも使いません。「unstable（安定でない）」はバグがあるという意味ではありません。比べると等しい要素どうしが、入れ替わるかもしれないという意味です。ただの数値や文字列なら違いはわからないので、普段使いにぴったりです。

逆順に並べる

大きい順に並べる方法は、よく使うものが3つあります。ここでは、どれも同じ結果になります。

use std::cmp::Reverse;

fn main() {
    let mut a = vec![3, 8, 1, 5];
    a.sort();
    a.reverse();
    println!("{:?}", a);

    let mut b = vec![3, 8, 1, 5];
    b.sort_by(|x, y| y.cmp(x)); // xより先にyを書く = 降順
    println!("{:?}", b);

    let mut c = vec![3, 8, 1, 5];
    c.sort_by_key(|&n| Reverse(n));
    println!("{:?}", c);
}

実行結果:

[8, 5, 3, 1]
[8, 5, 3, 1]
[8, 5, 3, 1]

▶ 実際に試してみよう

x.cmp(y) は Ordering を返します。値は Less（小さい）、Equal（等しい）、Greater（大きい）のどれかです。sort_by はこれを使って、どちらの要素を先にするかを決めます。y.cmp(x) と書くとすべての判断が逆になるので、全体の順番も逆になります。Reverse は std::cmp にある小さなラッパーで、キーに対して同じように逆転させてくれます。

浮動小数点数を並べ替える

f64 のベクタに .sort() を使おうとすると、Rustに断られます。

fn main() {
    let mut prices = vec![2.5, 0.99, 10.0];
    prices.sort();
}

error[E0277]: the trait bound `{float}: Ord` is not satisfied
 --> src/main.rs:3:12
  |
3 |     prices.sort();
  |            ^^^^ the trait `Ord` is not implemented for `{float}`

コンパイラは「浮動小数点数には Ord トレイトが実装されていない」と言っています。なぜでしょうか。.sort() には全順序（Ord トレイト）が必要です。つまり、どんな2つの値でも、一方が小さいか、等しいか、大きいかのどれかでなければなりません。ところが浮動小数点数には NaN（「数ではない」という意味の特別な値）があり、これは何に対しても、自分自身に対してさえ、小さくも等しくも大きくもありません。そのため浮動小数点数には PartialOrd しかなく、.partial_cmp() は Option<Ordering> を返し、NaN のときは None になります。

よい直し方が2つあります。

fn main() {
    let mut prices = vec![2.5, 0.99, 10.0, 4.75];

    // NaNがないと確信できる場合:
    prices.sort_by(|a, b| a.partial_cmp(b).unwrap());
    println!("{:?}", prices);

    // NaNがあっても動く（NaNは最後に来る）:
    let mut readings = vec![3.2, f64::NAN, -1.0, 0.5];
    readings.sort_by(|a, b| a.total_cmp(b));
    println!("{:?}", readings);
}

実行結果:

[0.99, 2.5, 4.75, 10.0]
[-1.0, 0.5, 3.2, NaN]

▶ 実際に試してみよう

partial_cmp(...).unwrap() は、NaN に出会うとパニックします。total_cmp は、NaN も含めてすべての浮動小数点数の位置を決めているので、パニックしません。特に理由がなければ total_cmp を使いましょう。

sort_by_keyと構造体の並べ替え

sort_by_key は、何で並べ替えるかを選ぶクロージャを受け取ります。フィールドを選んで並べられるので、構造体にぴったりです。

#[derive(Debug)]
struct Product {
    name: String,
    price_cents: u32,
}

fn main() {
    let mut items = vec![
        Product { name: String::from("pen"), price_cents: 150 },
        Product { name: String::from("Notebook"), price_cents: 499 },
        Product { name: String::from("eraser"), price_cents: 75 },
    ];

    items.sort_by_key(|p| p.price_cents);
    for p in &items {
        println!("{} - {}", p.price_cents, p.name);
    }

    items.sort_by_key(|p| p.name.to_lowercase());
    let names: Vec<&str> = items.iter().map(|p| p.name.as_str()).collect();
    println!("{:?}", names);
}

実行結果:

75 - eraser
150 - pen
499 - Notebook
["eraser", "Notebook", "pen"]

▶ 実際に試してみよう

キーを返すクロージャは、所有された値を返さなければなりません。p.price_cents は u32 でコピーされるので、問題ありません。String のフィールドなら新しい String が必要です。2回目の並べ替えで to_lowercase() を使っているのはそのためで、これが新しい String を作ってくれます（下の「よくある間違い」も見てください）。商品名を英語のままにしているのは、大文字・小文字を区別しない並べ替えの効果を見てもらうためです。

複数のフィールドで並べ替える

定番の課題です。生徒を成績の高い順に並べ、成績が同じ生徒どうしは名前のA→Z順に並べたい。こういうときは sort_by と .then_with() を使います。.then_with() は、最初の比較が引き分けだったときだけ、2つ目の比較を見ます。

struct Student {
    name: String,
    grade: u32,
}

fn main() {
    let mut class = vec![
        Student { name: String::from("Liam"), grade: 88 },
        Student { name: String::from("Ava"), grade: 95 },
        Student { name: String::from("Noah"), grade: 88 },
        Student { name: String::from("Emma"), grade: 88 },
        Student { name: String::from("Mia"), grade: 72 },
    ];

    class.sort_by(|a, b| {
        b.grade.cmp(&a.grade)               // 成績: 高い順
            .then_with(|| a.name.cmp(&b.name)) // 次に名前: A→Z
    });

    for s in &class {
        println!("{:>3}  {}", s.grade, s.name);
    }
}

実行結果:

 95  Ava
 88  Emma
 88  Liam
 88  Noah
 72  Mia

▶ 実際に試してみよう

もっと短く書くなら、キーとしてタプルを返す方法もあります。タプルは、まず1つ目の要素を比べ、次に2つ目、という順番で比べられます。

class.sort_by_key(|s| (Reverse(s.grade), s.name.clone()));

これでもまったく同じ順番になります。すっきりしていますが、すべての名前を clone するので、大きなリストでは sort_by と then_with を使う習慣をつけたほうがよいでしょう。

dedupで重複を取り除く

.dedup() は、すぐ前の要素と等しい要素を取り除きます。そのため、重複をすべて取り除けるのは、先にリストを並べ替えたときだけです。

fn main() {
    let mut tags = vec!["rust", "web", "rust", "cli", "web", "web"];

    let mut not_sorted = tags.clone();
    not_sorted.dedup();
    println!("dedupだけ: {:?}", not_sorted);

    tags.sort();
    tags.dedup();
    println!("sortしてからdedup: {:?}", tags);
}

実行結果:

dedupだけ: ["rust", "web", "rust", "cli", "web"]
sortしてからdedup: ["cli", "rust", "web"]

▶ 実際に試してみよう

1回目（dedupだけ）でまとめられたのは、隣り合っていた2つの "web" だけでした。先に並べ替えて、それから dedup しましょう。もとの順番を残したいなら、HashSet のページで紹介した HashSet を使う方法があります。

検索: contains、position、max、min、binary_search

よく使う検索の道具を紹介します。

• contains(&x) — 含まれている？ bool を返します。
• iter().position(...) — 最初に条件に合うのはどこ？ Option<usize> を返します。
• iter().max() / iter().min() — 最大と最小を Option で返します（空のリストなら None）。
• iter().max_by_key(...) / min_by_key(...) — あるフィールドで見たときの最大や最小を返します。
• binary_search(&x) — とても速い検索（二分探索）ですが、並べ替え済みのリストでしか使えません。見つかれば Ok(index) を、見つからなければ、その値が入るはずの位置を Err(index) で返します。

fn main() {
    let temps = vec![18, 25, 12, 31, 25];
    println!("31はある？ {}", temps.contains(&31));
    println!("20を超える最初の位置: {:?}", temps.iter().position(|&t| t > 20));
    println!("最大: {:?}、最小: {:?}", temps.iter().max(), temps.iter().min());

    let players = vec![("ana", 340), ("ben", 515), ("chen", 220)];
    let best = players.iter().max_by_key(|(_, score)| *score).unwrap();
    println!("トップの選手: {}", best.0);

    let mut sorted = vec![10, 20, 30, 40];
    println!("{:?}", sorted.binary_search(&30));
    let missing = sorted.binary_search(&25);
    println!("{:?}", missing);
    if let Err(pos) = missing {
        sorted.insert(pos, 25); // リストは並んだまま
    }
    println!("{:?}", sorted);
}

実行結果:

31はある？ true
20を超える最初の位置: Some(1)
最大: Some(31)、最小: Some(12)
トップの選手: ben
Ok(2)
Err(2)
[10, 20, 25, 30, 40]

▶ 実際に試してみよう

binary_search は真ん中の要素を調べ、値が入っているはずのない半分を捨て、それを繰り返します。100万個の要素があるリストでも、最大100万回ではなく、20回ほど調べるだけで済みます。Err(pos) という答えも便利です。pos の位置に挿入すれば、リストは並んだままになります。

注意

max() と min() も Ord が必要なので、浮動小数点数には使えません。代わりに max_by(|a, b| a.total_cmp(b)) を使いましょう。並べ替えのときと同じ直し方です。

よくある間違い

sort_by_key から、借用している String フィールドを返してしまう。 自然に見えますが、コンパイルできません。

students.sort_by_key(|s| s.name);

error[E0507]: cannot move out of `s.name` which is behind a shared reference
  --> src/main.rs:12:30
   |
12 |     students.sort_by_key(|s| s.name);
   |                              ^^^^^^ move occurs because `s.name` has type `String`, which does not implement the `Copy` trait

このエラーは「共有参照の向こうにある s.name をムーブすることはできない」という意味です。クロージャは各生徒を借用しているだけなので、String を手放すことはできません。clone する（|s| s.name.clone()）か、sort_by(|a, b| a.name.cmp(&b.name)) を使ってコピーそのものを避けましょう。

並べ替えていないリストに binary_search を使ってしまう。 クラッシュはしませんが、答えに意味がなくなります。値がちゃんとそこにあるのに、見つからないと言われることもあります。必ず先に並べ替えるか、代わりに contains / position を使いましょう。

練習問題

1. ランキング表

プレイヤーが (name, score) のタプルで並んでいます：("ben", 70)、("ana", 95)、("chen", 70)、("dev", 88)、("eli", 60)。スコアの高い順に並べ替え、同点のときは名前のアルファベット順（AからZ）にしてください。表示するのは上位3人だけです。ヒント：sort_by と .then_with() を使い、上位3人はスライス &players[..3] で取り出します。

解答を見る

fn main() {
    let mut players = vec![("ben", 70), ("ana", 95), ("chen", 70), ("dev", 88), ("eli", 60)];

    players.sort_by(|a, b| b.1.cmp(&a.1).then_with(|| a.0.cmp(&b.0)));

    for (name, score) in &players[..3] {
        println!("{score} {name}");
    }
}

実行結果:

95 ana
88 dev
70 ben

▶ 実際に試してみよう

タプルでは、.0 が名前、.1 がスコアです。ben と chen はどちらも70点なので名前で順位が決まり、ben が上位3人に入ります。

2. 価格の中央値

価格 3.5, 1.25, 9.0, 4.75, 2.0 の中央値（真ん中の値）を求めてください。並べ替えたリストと中央値を表示します。ヒント：total_cmp で並べ替えます。要素数が奇数のリストなら、真ん中の要素はインデックス len() / 2 にあります。

解答を見る

fn main() {
    let mut prices: Vec<f64> = vec![3.5, 1.25, 9.0, 4.75, 2.0];

    prices.sort_by(|a, b| a.total_cmp(b));
    let median = prices[prices.len() / 2];

    println!("並べ替え後: {:?}", prices);
    println!("中央値: {median}");
}

実行結果:

並べ替え後: [1.25, 2.0, 3.5, 4.75, 9.0]
中央値: 3.5

▶ 実際に試してみよう

Vec<f64> という型注釈が大事です。これがないと、total_cmp のところでRustは数値がどの浮動小数点型なのかまだわからず、“no method named total_cmp”（total_cmp というメソッドがない）というエラーでコンパイルを拒否します。

まとめ

• sort() と sort_unstable() は、その場で小さい順に並べ替えます。大きい順にするには reverse()、y.cmp(x)、Reverse を使います。
• 浮動小数点数は NaN があるので sort() を使えません。sort_by(|a, b| a.total_cmp(b)) を使いましょう。
• sort_by_key は選んだフィールドで並べ替えます。sort_by と .then_with() で、複数のフィールドで並べ替えられます。
• dedup() が取り除くのは、隣り合った等しい要素だけです。先に並べ替えましょう。
• contains、position、max/min、max_by_key はどんなリストでも検索できます。binary_search はずっと速いですが、並べ替え済みのリストが必要です。

理解度チェック

理解度チェック

1. vec![1.5, 0.5].sort() がコンパイルできないのはなぜですか？

浮動小数点数は Vec に入れられないから sort は文字列にしか使えないから NaN を比べられないので、浮動小数点数は Ord を実装していないから ベクタが mut ではないから

2. vec![1, 1, 2, 1].dedup() のあと、ベクタには何が残りますか？

[1, 2] [1, 2, 1] [2] [1, 1, 2, 1]

3. vec![10, 20, 30].binary_search(&25) は何を返しますか？

Err(2) Ok(2) None -1

4. a.grade.cmp(&b.grade).then_with(|| a.name.cmp(&b.name)) で、名前が比べられるのはいつですか？

いつも、成績より先に 一度も比べられない 名前が違うときだけ 2人の成績が等しいときだけ

スコア: 0 / 4

さらに詳しく

• スライスのメソッド: sort、sort_by、binary_search など — 標準ライブラリのドキュメント（英語）：並べ替えと検索のメソッドがすべて載っています。速さや安定性についての説明もあります。
• std::cmp::Ordering — 標準ライブラリのドキュメント（英語）：Less、Equal、Greater と、then、then_with、reverse について。
• std::cmp::Reverse — 標準ライブラリのドキュメント（英語）：キーを大きい順に並べ替えるためのラッパーです。
• f64::total_cmp — 標準ライブラリのドキュメント（英語）：浮動小数点数を並べ替えたとき、NaN、マイナスゼロ、無限大がどこに来るのかが正確にわかります。
• Sort a Vector — Rust Cookbook（英語）：整数、浮動小数点数、構造体を並べ替える短いレシピ集です。