昨日に引き続き、JavaScriptの配列の話です¹。そして、ECMA-262の仕様書では昨日ソースコードに展開したArray.prototype.sliceの次に当たる、Array.prototype.sortに関する話です。

デフォルトでの挙動

何も指定せずに.sort()を実行すると、中身の文字列表現に対して並べ替えを行うこととなります。また、EcmaScriptとしてはソートが安定であることは保証されません（関連）²。

もちろんこれで事足りればそれでもいいのですが、数値やオブジェクトなどを並べ替えるには、このままでは全く役に立ちません。

実装定義となってしまう場合

そうなれば、引数として比較関数を与えることになるのですが、その前に実装定義な部分について考えておきましょう。

まず、具体的なソートアルゴリズムには何も言及がなく、実装定義で好きなように実装できます（もちろん、結果については仕様で決まっているので、それが定める結果を生成する必要はあります）。

また、0〜length-1のプロパティの中に以下のようなプロパティがある場合、振る舞いは実装定義となります。

Object.definePropertyなどでWritableをfalseにしたもの
アクセサプロパティ

また、疎な配列の場合、並べ替え後も疎な配列となることになっています。ただし、疎な配列については、以下のいずれかような場合、振る舞いは実装定義となります。

0〜length-1のプロパティの中に、プロトタイプから継承したものがある
Object.preventExtension()などで拡張不可となっている
0〜length-1のプロパティの中に、Object.definePropertyなどでConfigurableをfalseにしたものがある

比較関数について

比較関数を指定する場合、その関数が以下のような挙動を示す場合、sortの振る舞いは実装定義となります。

配列自体を書き換えてしまう
正の数、負の数、0のどれでもない値を返す
両方に同じ引数を与えた時に、0以外の値を返す
同じ引数のペアを与えた時に、違う値を返すことがある
推移則を満たさない（$a < b$かつ$b < c$なのに$a = c$や$a > c$という結果を返してしまうなど）

実装定義って？

ECMAの仕様書ではC言語の仕様も参照するようになっていたのでそちらも確認したのですが、

処理系定義の動作（implementation-defined behavior）未規定の動作のうち，各処理系が選択した動作を文書化するもの。
未規定の動作（unspecified behavior）この規格が，二つ以上の可能性を提供し，個々の場合にどの可能性を選択するかに関して何ら要求を課さない動作。

というようになっています。JavaScriptの場合、各処理系がどのような動作をするのか明確に文書化されていることをみることは少ないのですが、とりわけクライアントサイドで使う場合、実装を選ぶことが難しいという事情があります。そして、sortでの「振る舞いは実装定義」となっているものは、「出力は入力の並べ替え」より前に来ていますので、並べ替えであることすら保証されません。例外を投げておしまい、なんてことも考えられますし、そのような領域に入り込むようなコードは、基本的には書くべきでないでしょう。

数値の比較関数〜タイトル回収

で、数値を並べ替えるような場合、よく下のような比較関数が使われます（MDNにも載っていました）。

比較関数の例

arr.sort(function(a, b){ return a - b; });

arrに数値が入っているのは前提とするにしても、このままではうまく動かない事例が出てきます。

先ほど、比較関数が「正の数、負の数、0のどれでもない値を返す」場合は実装定義となる、と書きました。もちろん返り値が数値でなければこれを満たしてしまうのですが、実は数値にも、1つだけ「正でも負でも0でもない」数（？）があります。NaNです。

JavaScriptに限らず、IEEE 754で浮動小数点数を実装している環境にはたいていNaNがありますが、相当に特殊な数です。

NaN === NaNがfalse（JavaScriptの値の中で、x !== xとなるものはNaNのみです）
NaN > (任意の数)、NaN < (任意の数)、NaN == (任意の数)、すべてがfalse
NaNと他の値との四則演算も、すべて結果がNaN

つまり、元の配列にNaNが1つでも入っていれば、比較関数もNaNを返してしまい、.sort()は結果を何も保証しなくなってしまいます³。ということで、NaNが入りうる場合、それを考えて比較関数を書く必要があります（なお、無限大は正負の符号を付けられることからわかるように、比較関数の返り値としてもなんら問題ありません）。NaNが来る可能性があるなら、それを意識した比較関数を書く必要があります。

NaNを最後にした昇順

arr.sort(function(a, b){
  var a_nan = (a !== a);
  var b_nan = (b !== b);
  if (a_nan && b_nan) return 0;
  if (a_nan) return 1;
  if (b_nan) return -1;
  //ここまで来ればaもbもNaNの可能性はない
  if (a < b) return -1;
  if (a > b) return 1;
  return 0;
});

昨日の件とは全く別な事情で知ったことなのですが、不思議と近い分野のことが連続していろいろと起きる気がします。 ↩
Firefoxでは安定性を保証してくれるそうです。 ↩
実際にうっかり使ってしまったのですが、NaNでない値の順序すら不定となりました。 ↩

「配列がうまくsortできない！」「な、何だってー！」

デフォルトでの挙動

実装定義となってしまう場合

比較関数について

実装定義って？

数値の比較関数〜タイトル回収