【整列】 | アルゴリズム

この章では並び替えを扱います。前半はよく使う並び替え: 比較関数を自在に書けるようになる(実務とテストで毎日使う技術)。後半は応用: 並べ替えそのものを一度手で書いて、sortの中で何が起きているかを覗きます。

比較関数の正体

おさらいから。数値の配列を引数なしでsortすると文字列の辞書順になってしまうため、比較関数を渡すのでした。

nums.sort((a, b) => a - b);   // 昇順

この (a, b) => a - b が何者なのか、今日は正体を明かします。sortは並べ替えの最中、「aとb、どちらが前?」という質問を何度も比較関数に投げます。比較関数は戻り値の符号で答えます。

a - b が昇順になる理由は、これで読めます。たとえばa=2, b=10なら、2−10=−8(負)なので「aが前」。小さい方が常に前に来る=昇順。b - a にすれば符号が逆転して降順。引き算は「符号で答える」を一番短く書く方法だった、というわけです。

符号のルールを、極端な比較関数で確かめます。

1つ目は元の順の維持または反転(エンジンの質問の仕方に依存します)、2つ目は元の順のまま、「全部同順」と答えれば、sortは何も動かしません。比較関数が並べ替えの判断のすべてを握っていることが分かります。

比較関数の本領は、オブジェクトの配列です。「どの項目で並べるか」を自分で決められます。

数値の項目は引き算、文字列の項目は localeCompare(「aがbより辞書順で前なら負を返す」メソッド。日本語もおおむね自然に並びます)。この2つの型で、実務のソートの大半は書けます。

もうひとつ、覚えておくと面接やテストで効く形が、複数条件のソートです。「価格の安い順、同価格なら在庫の多い順」:

products.sort((a, b) => a.price - b.price || b.stock - a.stock);

|| は「左が0(=同順)のときだけ、右を評価する」と読めます。第1条件で決着がつかないときだけ第2条件へ。条件の優先順位が、そのまま || の並び順になります。

なお、sortは破壊的メソッドです(元の配列が並び替わる)。元を保ちたいときは toSorted を使うのでした。上の実行枠で [...nums] とコピーしてからsortしていたのは、そのためです。