5

Mac版Chrome(42.0.2311.135 64-bit)で、
自前の比較関数を用いて文字列配列のソートをすると変な結果になります。

以下から試せます。

var arr1 = ["hoge0", "piyo0", "fuga0", "fuga1", "fuga2", "fuga3", "fuga5", "fuga6", "fuga7", "fuga8"];
var arr2 = ["hoge0", "piyo0", "fuga0", "fuga1", "fuga2", "fuga3", "fuga5", "fuga6", "fuga7", "fuga8", "fuga9"];
var compare = function(a, b){
  return a > b;
};

document.body.innerHTML += '1) ' + arr1.sort(compare).join(',') + '<br>';
document.body.innerHTML += '2) ' + arr2.sort(compare).join(',') + '<br>';
document.body.innerHTML += '3) ' + arr2.sort().join(',');

Firefoxなら2)と3)が同じ結果になるのですが、
Chromeで実際に実行すると以下の結果になります。2)が変です。

1) fuga0,fuga1,fuga2,fuga3,fuga5,fuga6,fuga7,fuga8,hoge0,piyo0
2) fuga3,fuga9,fuga0,fuga1,fuga2,fuga8,fuga5,fuga6,fuga7,hoge0,piyo0
3) fuga0,fuga1,fuga2,fuga3,fuga5,fuga6,fuga7,fuga8,fuga9,hoge0,piyo0

これはバグなのでしょうか?それともソートの仕方が間違っているのでしょうか?

2 件の回答 2

9

比較関数には

1つ目の引数が2つ目の引数よりも小さい場合は、負の値を返す。
2つの引数が等しい場合は0を返す。
1つ目の引数が2つ目の引数よりも大きい場合は、正の値を返す。

必要があります。
なので、示された比較関数は正確にはこの条件を満たしていません。
例えば、以下のようにする必要があります。
var compare = function(a,b){ return (a > b) - (a < b); };

1
  • あああ、なぜかブール値返すものと勘違いしていました。 比較関数の書き方参考になります。ありがとうございます。
    – tkrkt
    Commented 2015年5月10日 12:07
4

比較関数の戻り値については既出の通りです。

しかし、オブジェクトのソートを行う場合で、各種ブラウザ間でソート結果を同じにしたい場合は、0を返さないようにする必要があります。Chromeのソートは(配列の要素数によっては)安定ソートになりません。

要するに、比較関数が return 0 した場合、ブラウザによっては並び替えたり、並び替えなかったりするということです。

以下のスニペットを実行すると、ソート結果の違いが分かります。

function unstableSort(a, b) {
  return a.x - b.x;
}

function stableSort(a, b) {
  if (a.x === b.x) {
    return indexed.indexOf(a) - indexed.indexOf(b);
  }

  return unstableSort.call(this, a, b);
}

function display(title, items) {
  var div = $('<div />'),
    ol = $('<ol />');

  div.append('<h1>' + title + '</h1>').append(ol);

  items.forEach(function(item, index) {
    ol.append('<li>(' + item.x + ', ' + item.y + ')</li>');
  });

  $('body').append(div);
}

var items = [{
      x: 1,
      y: 1
    }, {
      x: 1,
      y: 2
    }, {
      x: 1,
      y: 3
    }, {
      x: 1,
      y: 4
    },
    {
      x: 1,
      y: 5
    }, {
      x: 1,
      y: 6
    }, {
      x: 1,
      y: 7
    }, {
      x: 1,
      y: 8
    },
    {
      x: 1,
      y: 9
    }, {
      x: 1,
      y: 10
    }, {
      x: 1,
      y: 11
    }
  ],
  indexed = items.slice(0);

items.sort(unstableSort);
display('Unstable', items);

items.sort(stableSort);
display('Stable', items);
body>div {
  width: 49%;
  display: inline-block;
}
<p><em>This demo is designed to be run in Chrome -- the latest version of FireFox (as at 02/07/2014) and IE10 both implement stable sorting, at least for an array of the size used here.  Chrome's (v35) sort is stable for an array of up to 10 elements as it uses the Insertion Sort algorithm (which is stable); for arrays of greater than 10 elements, it uses a non-stable version of the QuickSort algorithm.</em></p>

1
  • 初めて知りました。確かにこう書いてます。 結構これ知らないとハマりそうですね。 developer.mozilla.org/ja/docs/Web/JavaScript/Reference/… compareFunction(a, b) が 0 を返す場合、a と b は互いに関して変えることなく、他のすべての要素に関してソートします。注意: ECMAScript 標準はこの振る舞いを保証しておらず、そのため一部のブラウザ (例えば、遅くとも 2003 年以前のバージョンの Mozilla) はこれを尊重していません。
    – tkrkt
    Commented 2015年5月12日 0:20

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。