RustのVecをソートする方法：sortとsort_unstableの使い分けを事例で学ぶ

Rustでデータを効率的に管理し、特定の順序で処理を行うためには、コレクション型である Vec のソート操作をマスターすることが不可欠です。

Rustの標準ライブラリは、高いパフォーマンスと安全性を両立させた強力なソートアルゴリズムを提供しています。

しかし、標準ライブラリには sort と sort_unstable という2つの主要なメソッドが存在し、どちらを選択すべきか迷う場面も少なくありません。

本記事では、これら2つのメソッドの内部的な仕組みから具体的な使い分け、さらに複雑な構造体や浮動小数点のソート方法までを詳しく解説します。

Rustにおけるソートの基本：sortメソッド

まずは、最も基本的で安全な選択肢である sort メソッドについて見ていきましょう。

sort メソッドは、要素を昇順に並べ替えるための標準的な手段です。

このメソッドの最大の特徴は、「安定ソート (Stable Sort)」であるという点にあります。

安定ソートとは、ソートキーが同じ値を持つ要素が複数ある場合に、ソート前と同じ相対的な順序を維持することを保証するアルゴリズムです。

例えば、名前順でソートされた名簿を年齢順で再ソートした際、同じ年齢の人の間では名前順が維持されます。

Rustの sort メソッドは、内部的に DriftSort と呼ばれる高度なアルゴリズムを採用しています。

DriftSortは、マージソートと挿入ソートを組み合わせたようなハイブリッドアルゴリズムであり、既存の順序を最大限に活用して高速化を図ります。

安定性を維持するために、ソート中に追加のメモリ割り当て (一時的なバッファ) を行う可能性がある点に注意してください。

sortメソッドの基本的な使い方

基本的な数値のベクトルをソートする例を確認してみましょう。

// 数値のベクトルを作成
let mut numbers = vec![10, 5, 8, 3, 1];

// sortメソッドを呼び出す(ミュータブルな参照が必要)
numbers.sort();

println!("Sorted: {:?}", numbers);

Sorted: [1, 3, 5, 8, 10]

sort メソッドを呼び出すためには、対象となる Vec が mut (ミュータブル) である必要があります。

パフォーマンス重視の選択肢：sort_unstableメソッド

次に、パフォーマンスを最優先する場合に使用される sort_unstable メソッドについて解説します。

sort_unstable は、その名の通り「不安定ソート (Unstable Sort)」を行うメソッドです。

不安定ソートでは、同じ値を持つ要素の相対的な順序がソート後に変わってしまう可能性があります。

しかし、安定性を考慮する必要がない分、sort メソッドよりも高速に動作し、追加のメモリ割り当てをほとんど行わないという強力なメリットがあります。

内部アルゴリズムには、パターン認識型のクイックソートである IPNSort (Instruction-Parallel Network Sort) などの改良版が使用されています。

現代のプロセッサの予測実行やキャッシュ効率を最大限に引き出すように設計されており、大規模なデータの処理において顕著な差が出ます。

単純な数値や、要素の順序が入れ替わっても問題ない構造体を扱う場合は、基本的に sort_unstable を選択するのがRustのベストプラクティスです。

sort_unstableメソッドの使いどころ

以下のコードは、大量の整数データを高速にソートする例です。

let mut data = vec![100, 20, 50, 20, 10];

// 同じ値「20」の順序を気にしないならunstableが最適
data.sort_unstable();

println!("Unstable Sorted: {:?}", data);

Unstable Sorted: [10, 20, 20, 50, 100]

この場合、2つの「20」が入れ替わったとしても結果に違いはないため、速度に優れる sort_unstable が推奨されます。

sort と sort_unstable の比較表

それぞれのメソッドの特性を理解しやすくするために、主要な違いを以下の表にまとめました。

特定の条件でソートする：sort_by と sort_by_key

単なる数値の比較だけでなく、より複雑なデータ構造やカスタムロジックでソートしたい場合があります。

その際に便利なのが、sort_by と sort_by_key です。

sort_by：クロージャで詳細な比較を行う

sort_by は、2つの要素を引数に取るクロージャを渡し、その比較結果 (Ordering) を返すことでソート順を決定します。

let mut values = vec![5, 2, 8, 1, 9];

// 降順(大きい順)でソートする
values.sort_by(|a, b| b.cmp(a));

println!("Descending: {:?}", values);

Descending: [9, 8, 5, 2, 1]

このメソッドは、標準の Ord トレイト以外の基準で並べ替えたい場合に非常に強力です。

sort_by_key：特定のフィールドをキーにする

構造体の特定のフィールドを基準にソートする場合、sort_by_key を使うとコードを簡潔に記述できます。

#[derive(Debug)]
struct User {
    name: String,
    age: u32,
}

let mut users = vec![
    User { name: "Alice".to_string(), age: 30 },
    User { name: "Bob".to_string(), age: 25 },
    User { name: "Charlie".to_string(), age: 35 },
];

// 年齢をキーにしてソート
users.sort_by_key(|u| u.age);

println!("Sorted by age: {:?}", users);

Sorted by age: [User { name: "Bob", age: 25 }, User { name: "Alice", age: 30 }, User { name: "Charlie", age: 35 }]

ただし、sort_by_key に渡すクロージャの中で、所有権の移動が発生するような値(String型のクローンなど)を返すと、パフォーマンスが低下する可能性があるため注意しましょう。

浮動小数点のソートにおける注意点

Rustで f32 や f64 の Vec をソートしようとすると、コンパイルエラーが発生します。

これは、浮動小数点数には NaN (Not a Number) が存在するため、完全な順序 (Ord) を満たさず、部分的な順序 (PartialOrd) しか持たないためです。

Rustの sort メソッドは、要素が Ord トレイトを実装していることを要求します。

浮動小数点をソートするには、明示的に比較ロジックを指定する必要があります。

浮動小数点を安全にソートするコード例

let mut floats = vec![1.1, 5.5, 2.2, f64::NAN, 3.3];

// NaNが含まれている可能性があるため、unwrapを使わずに処理する
floats.sort_by(|a, b| a.partial_cmp(b).unwrap_or(std::cmp::Ordering::Equal));

println!("Floats Sorted: {:?}", floats);

実務上、データに NaN が含まれていないことが保証されている場合は、partial_cmp(b).unwrap() を使用するのが一般的です。

逆順にソートする効率的な方法

昇順ではなく降順にソートしたい場合、いくつかの手法があります。

一つは前述の sort_by(|a, b| b.cmp(a)) を使う方法ですが、もっとシンプルに reverse() を組み合わせる方法もあります。

let mut numbers = vec![1, 2, 3, 4, 5];

// 一旦昇順にソート
numbers.sort();
// 順序を反転させる
numbers.reverse();

しかし、要素数が多い場合は、ソートの過程で逆順にする sort_by を使う方が効率的です。

また、要素に std::cmp::Reverse をラップする方法もあります。

use std::cmp::Reverse;

let mut data = vec![1, 5, 2, 8];
// Reverseでラップしてソートすることで降順にする
data.sort_by_key(|&x| Reverse(x));

パフォーマンスを最大化するためのヒント

Rustのソートを最適化するために、以下のポイントを意識してください。

• 基本的には sort_unstable を選ぶ：安定性が必要ない限り、これが最も高速です。
• メモリ割り当てを減らす：sort は一時的なメモリを確保しますが、sort_unstable はそれを回避します。
• sort_by_cached_key を活用する：ソートキーの計算が非常に重い(例：複雑な計算や文字列変換)場合は、計算結果をキャッシュするこのメソッドを検討してください。
• 並列ソートを検討する：非常に巨大なデータをソートする場合、標準ライブラリではなく rayon クレートの par_sort を使用することで、マルチコアを活用した超高速化が可能です。

まとめ

Rustの Vec におけるソートは、要件に応じて柔軟に使い分けることが重要です。

要素の相対的な順序を保持する必要があるなら sort を、スピードとメモリ効率を重視するなら sort_unstable を選択しましょう。

また、構造体や浮動小数点といった特殊な型を扱う場合は、sort_by や sort_by_key を活用することで、自由自在に並べ替えロジックを実装できます。

Rustが提供するこれらのメソッドは、いずれも最新のアルゴリズムに基づいて最適化されており、安全かつ高速なプログラミングを強力にサポートしてくれます。

まずは sort_unstable を試してみて、必要に応じて他のメソッドに切り替えていくというアプローチが、モダンなRust開発における賢明な選択と言えるでしょう。