比較関数つきソート｜コードで実践

比較関数つきソート

このレッスンで分かること

ソートの本質は「2 要素のうち、どちらが前に来るべきか」のルール

実務でソートを使うときの多くは、単純な昇順ではなく 「ある観点で並べ替える」 です

これを実現するのが 比較関数 (comparator) または key 関数を渡す方式 です

比較関数つきソートとは

ソート順を自分で定義する比較関数 / key 関数を実装し、絶対値順や複数キー順を扱う。本レッスンでは、比較関数つきソートの基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。

実務でソートを使うときの多くは、単純な昇順ではなく 「ある観点で並べ替える」 です。

商品を 価格の安い順 に並べる
文字列を 長さの短い順 に並べる
二次元の点を x 座標 -> y 座標 の順に並べる
数値を 絶対値の小さい順 に並べる

これを実現するのが 比較関数 (comparator) または key 関数を渡す方式 です。本レッスンでは「絶対値の小さい順、絶対値が同じなら元の値の小さい順」で並べる関数を実装します。

ソートの本質は「2 要素のうち、どちらが前に来るべきか」のルール。これを差し替えれば任意の順序で並べられる。

入出力の例

入力: [3, -1, -4, 1, 5, -9, 2, 6]
出力: [-1, 1, 2, 3, -4, 5, 6, -9]

絶対値で比べると 1, 1, 2, 3, 4, 5, 6, 9 の順。ただし絶対値 1 のものは 2 つあり、その中では 元の値が小さい順 で -1 -> 1 の並びになります。

diagram (will load when visible)

図のポイント (テキスト併記)

比較関数を書くときは「タイブレーク (同点処理) のルール」も明示するのが重要

比較関数を書くときは「タイブレーク (同点処理) のルール」も明示するのが重要。

Python (key 関数で書く)

Python の sorted は key=... を受け取って 要素ごとに 1 度だけキーを計算 し、その値で並べます。タプルを返せば自然に 2 段比較 ができます。

Python

def sortByKey(arr):
    return sorted(arr, key=lambda x: (abs(x), x))

(abs(x), x) というタプルが返ると、Python は最初に絶対値で比較し、同じならその次に値で比較してくれます。これが タプル比較 の便利なところです。

JavaScript (comparator で書く)

JS の sort は 比較関数 を受け取ります。返り値は 負なら a を前、0 なら同じ、正なら b を前。

JavaScript

function sortByKey(arr) {
  return [...arr].sort((a, b) => {
    const da = Math.abs(a) - Math.abs(b);
    if (da !== 0) return da;
    return a - b;
  });
}

絶対値で差を取り、同じなら元の値で差を取る、というルール。Math.abs(a) - Math.abs(b) のように 引き算で 負/0/正 を作る のは JS の典型イディオム。

比較関数の落とし穴

比較関数を書くときに守らなければならない 3 つの数学的性質 があります。

反射性: cmp(a, a) === 0
反対称性: cmp(a, b) > 0 なら cmp(b, a) < 0
推移性: cmp(a, b) <= 0 かつ cmp(b, c) <= 0 なら cmp(a, c) <= 0

この 3 つを破ると、ソートの結果が 環境依存で予測不可能 になります。よくあるバグが (a, b) => Math.random() - 0.5 でランダムシャッフルしようとするやつ。これは推移性を満たさず、Fisher-Yates を使うべきです。

比較関数は 数学的な順序 を定義する関数。3 性質を満たさないと未定義動作になる。

key 関数 vs comparator

方式	計算回数	書きやすさ	制約
key 関数	各要素 1 回 (= `n` 回)	シンプル	要素を変換して比較するだけ
comparator	比較ごと (= `n log n` 回)	自由度高い	3 性質を満たす必要

複雑なキーは key 関数のほうが速く、複数フィールドで柔軟に比べたいときは comparator のほうが書きやすい、という違いがあります。

よくある間違い

1 つ目は 比較関数で大小逆。(a, b) => a - b は昇順、(a, b) => b - a は降順。混乱しがちです。2 つ目は 不安定ソート前提のタイブレーク忘れ。現代の JS (ES2019+) や Python は安定ソートが保証されているため、同じキーの要素は入力順が維持されます。ただし入力順に依存したくない場合や別キーで明示的に並べたい場合は、タイブレークルールを書いて意図を明確にしましょう。3 つ目は 比較関数で true / false を返す。a < b で true を返してしまうと、JS では 1 扱いになって正しくソートされません。必ず数値の差分を返すこと。

やってみよう

(a, b) => b - a に変えて、降順絶対値ソートを書いてみる。
文字列の配列を 長さの短い順、同じならアルファベット順 に並べる関数を書く。
[(1, "a"), (2, "b"), (1, "c")] のような配列を「最初の要素昇順、同じなら 2 番目の要素降順」で並べる練習をする。

実務でよく使うパターン

業務システムで実際によく使うソート要件を 4 つ挙げます。

商品一覧を 人気度降順、同人気は新着順 で並べる
メッセージを 未読 -> 既読 の順、同じ既読状態なら新しい順
ユーザーを アクティブ -> 休眠、同状態内では登録日順
ログを 重大度順 -> 時刻順

どれも 2 段以上のキー が必要です。Python なら key=lambda x: (x.priority, -x.timestamp) のように マイナスをつけて逆順 にできるのが便利。JS なら || で連結する (a, b) => f1(a, b) || f2(a, b) イディオムが多用されます。

Schwartzian Transform

計算コストが高い key を持つソートでは Schwartzian Transform というテクニックがあります。元配列を (key, value) のタプルに変換 → key でソート → value だけ取り出す、という 3 ステップ。key を 要素ごとに 1 度だけ計算 することで n log n 回の比較中に何度も再計算する無駄を省きます。

Python の sorted(..., key=...) は内部的にこれを行ってくれます。JS の sort は 比較ごとに関数呼び出し するので、高コストな key を扱うときは自分で Schwartzian Transform を書くと体感速度が上がります。

比較関数で重い計算をしている場合、key 関数化または Schwartzian Transform でキー計算回数を n log n 回から n 回に削減できる。ソート自体は O(n log n) のまま。

よくある質問

Q. このトピックは実務でどう役立ちますか？

A. DB のクエリ最適化、API 設計、データ構造の選択など、設計判断の根拠になります。表面的にライブラリを使うだけでなく「なぜそれが速いのか」を理解できると、性能問題を未然に防げます。コーディング面接でも頻出のテーマです。

Q. 計算量はどう求めれば良いですか？

A. ループのネストごとに掛け算する、再帰なら漸化式から解く、というのが基本です。Big-O 表記は定数倍と低次の項を無視するため、n の指数（n²、n log n など）に注目してください。最悪・平均・最良の 3 つを意識すると説得力が増します。

Q. 覚えるべき定番アルゴリズムは何ですか？

A. 二分探索、クイックソート/マージソート、BFS/DFS、ダイクストラ、DP の基本問題（フィボナッチ・ナップサック）が必修です。これらを「白紙から書ける」状態にすると、応用問題が一気に解けるようになります。

次のレッスン

次は 第3章まとめクイズ で、ソート順を自分で定義する比較関数 / key 関数を実装し、絶対値順や複数キー順を扱うを学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

比較関数ソートの要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. 比較関数ソートとは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

比較関数つきソート