安定した Array.prototype.sort

公開日 · ECMAScript ES2019 のタグ付き

犬の配列があり、各犬に名前と評価がある場合を考えてみましょう。（これが奇妙な例に聞こえるなら、まさにこれを専門とするTwitterアカウントがあることを知っておくべきです…聞かないで！）

// Note how the array is pre-sorted alphabetically by `name`.
const doggos = [
  { name: 'Abby',   rating: 12 },
  { name: 'Bandit', rating: 13 },
  { name: 'Choco',  rating: 14 },
  { name: 'Daisy',  rating: 12 },
  { name: 'Elmo',   rating: 12 },
  { name: 'Falco',  rating: 13 },
  { name: 'Ghost',  rating: 14 },
];
// Sort the dogs by `rating` in descending order.
// (This updates `doggos` in place.)
doggos.sort((a, b) => b.rating - a.rating);

配列は、名前でアルファベット順に事前にソートされています。代わりに評価でソートする（評価の高い犬を最初に取得する）には、Array#sort を使用し、評価を比較するカスタムコールバックを渡します。これが、おそらく期待する結果です。

[
  { name: 'Choco',  rating: 14 },
  { name: 'Ghost',  rating: 14 },
  { name: 'Bandit', rating: 13 },
  { name: 'Falco',  rating: 13 },
  { name: 'Abby',   rating: 12 },
  { name: 'Daisy',  rating: 12 },
  { name: 'Elmo',   rating: 12 },
]

犬は評価でソートされていますが、各評価内では、名前でアルファベット順にソートされています。たとえば、チョコとゴーストは同じ評価の14を持っていますが、チョコはソート結果でゴーストよりも前に表示されます。これは元の配列での順序でもあるためです。

ただし、この結果を得るためには、JavaScriptエンジンは任意のソートアルゴリズムを使用することはできず、いわゆる「安定ソート」である必要があります。長い間、JavaScriptの仕様ではArray#sortのソートの安定性を要求しておらず、代わりに実装に任されていました。そして、この動作が規定されていなかったため、このソート結果も得られる可能性がありました。ここでは、ゴーストが突然チョコよりも前に表示されます。

[
  { name: 'Ghost',  rating: 14 }, // 😢
  { name: 'Choco',  rating: 14 }, // 😢
  { name: 'Bandit', rating: 13 },
  { name: 'Falco',  rating: 13 },
  { name: 'Abby',   rating: 12 },
  { name: 'Daisy',  rating: 12 },
  { name: 'Elmo',   rating: 12 },
]

言い換えれば、JavaScript開発者はソートの安定性に依存することができませんでした。実際には、一部のJavaScriptエンジンが短い配列には安定ソートを使用し、大きな配列には不安定ソートを使用していたため、状況はさらに腹立たしいものでした。これは、開発者がコードをテストして安定した結果を確認したが、配列がわずかに大きくなると、本番環境で突然不安定な結果になるため、非常に混乱しました。

しかし、良いニュースがあります。私たちはArray#sortを安定させる仕様変更を提案し、それが受け入れられました。すべての主要なJavaScriptエンジンは、現在、安定したArray#sortを実装しています。これは、JavaScript開発者として心配するものが1つ減ったということです。素晴らしい！

（それと、TypedArrayに対しても同じことを行いました。そのソートも安定しました。）

注意: 仕様では安定性が必須になりましたが、JavaScriptエンジンは依然として好みのソートアルゴリズムを実装できます。たとえば、V8はTimsortを使用しています。仕様は特定のソートアルゴリズムを義務付けていません。

機能サポート #

安定したArray.prototype.sort #

この機能サポートリストについて

安定した %TypedArray%.prototype.sort #

この機能サポートリストについて