比較関数つきソート

「小さい順」が、欲しい並びとは限らない

並べ替えの道具は「小さい順」を知っています。でも実際に欲しいのは、価格の安い順、文字数の短い順、絶対値の小さい順のように、値そのものではない別のものさしで測った順序であることがほとんどです。

[3, -1, -4, 1] を絶対値の小さい順にすると [-1, 1, 3, -4] です。値の大小で並べた [-4, -1, 1, 3] とはまったく違います。だからといって道具を作り直す必要はありません。並べ替えには、何で比べるかを渡せるようになっています。

比べる前に、測り直したものを渡す

Python の sorted は key を受け取ります。各要素を 1 度だけ key に通し、返ってきた値のほうで並べます。

words = ["pear", "fig", "apple", "kiwi"]
print(sorted(words, key=len))
# ['fig', 'pear', 'kiwi', 'apple']

len が返した 4, 3, 5, 4 で並んだ結果です。元の文字列そのものは一度も比べていません。

JavaScript は流儀が少し違い、2 つを受け取ってどちらを前にするかを数値で答える関数を渡します。負なら第 1 引数が前、正なら第 2 引数が前、0 なら決めない、という約束です。

const words = ["pear", "fig", "apple", "kiwi"];
console.log([...words].sort((a, b) => a.length - b.length));
// ['fig', 'pear', 'kiwi', 'apple']

引き算の結果がそのまま負・0・正になるので、a.length - b.length の 1 行で条件を書き切れます。順序を逆にしたいなら引く向きを入れ替えます。

測った値が同じになったとき、誰も順番を決めていない

fig と ant はどちらも 3 文字です。len はどちらにも 3 を返すので、この 2 つのどちらを前にするかを、ものさしは何も言っていません。JavaScript の書き方でいえば 0、つまり「決めない」と答えたのと同じです。

ここを自分で決めたいなら、ものさしが 1 つでは足りないと考えます。1 つ目で差がつかなかったときに見る 2 つ目を用意するのです。文字数が同じならアルファベット順、絶対値が同じなら元の値の小さい順。引き分けの決着のつけ方まで含めて、はじめて順序が定まります。

同じ基準の要素どうしで元の順番を保つ性質を、安定と呼びます。Python の sorted では保証されています。ただし元の順番が欲しい順番とは限りません。例えば長さだけで並べると pear は kiwi より先のままです。長さが同じならアルファベット順にしたい、という意図があるなら二つ目の基準を明示してください。

よくある間違い

JavaScript の比較関数で (a, b) => a.length < b.length のように真偽値を返すことです。true は 1、false は 0 として扱われるため、「第 2 引数が前」と「決めない」の 2 通りしか伝わりません。並びは崩れるのに例外は出ないので、気づきにくい間違いです。必ず数値の差を返してください。

演習で使う書き方

本文では語の長さを並べ替えの基準にしました。演習は距離を第一基準、元の値を第二基準にします。比較関数は第一引数が先なら負、第二引数が先なら正、同じなら 0 を返す約束です。cmp_to_key と sorted の接続、絶対値を求める補助は用意してあり、二段階の比較を自分で書きます。

1. 絶対値を優先し、同じなら元の値を比較する処理を自分で実装する
2. 関数名と引数、入力と戻り値の形を保つ。説明つきの準備部分を使い、TODO の仮の処理を置き換える