jQueryのsort()は安定ソートですか？

Question

###質問
HTML要素をjQueryで並び替えるために、sort()が利用できるようなのですが、この関数は、JavaScriptのsort()と同等で不安定なソートなのでしょうか？というか・・・そもそもJavaScriptのArrayのSort()そのものなのでしょうか？

###実現したいこと
ソートしたい要素は2つのパラメータ（カテゴリ、id）を持っており、idでソートしたあと、カテゴリ毎にまとめるために、カテゴリーでソートしようとしています。

<div id="wrapper">
  <div id="10" data-category="A">A10</div>
  <div id="6" data-category="B">B6</div>
  <div id="1" data-category="B">B1</div>
  <div id="7" data-category="A">A7</div>
  <div id="3" data-category="C">C3</div>
  <div id="11" data-category="D">D11</div>
  <div id="8" data-category="C">C8</div>
  <div id="4" data-category="D">D4</div>
  <div id="9" data-category="A">A9</div>
  <div id="2" data-category="B">B2</div>
  <div id="5" data-category="A">A5</div>
</div>

var wrapper = $('#wrapper');

var element = wrapper.children().sort(function(a,b){
  var a_val = $(a).id;
  var b_val = $(b).id;

  return a_val - b_val;
});

element = element.sort(function(a,b){
  var a_val = $(a).data('category');
  var b_val = $(b).data('category');
  if a_val === b_val return 0;
  if a_val < b_val {
    return -1
  } else {
    return 1
  }
});

wrapper.append(element);

安定ソートであれば、上記のような処理で問題ないと思うのですが・・・

もし、Arrayのソートそのものであれば、Array.prototypeのsortを安定なソートになるよう書き換えれば良いのでしょうか？

Answer 1

JavaScript の sort() を使っているとすれば、安定か否かは実装依存です。ECMSScript の仕様上は不安定であるとしています。

ECMAScript 2016 Language Reference
22.1.3.25 Array.prototype.sort (comparefn)

The sort is not necessarily stable (that is, elements that compare equal do not necessarily remain in their original order)

※Mozilla 系のエンジンは安定だが Chrome V8 は不安定ソート（クイックソートで実装）だったような…

安定が必要であれば、ソートする前に「ソート前時点での順位」を追加しておいて、ソート時に「ソート前時点での順位」を並べ替え時の条件（の最後）に追加することで、実装に関わらず安定化させることができるでしょう。

Comments

[Meganezaru]

ご回答ありがとうございます！

検索した感じでは、Chromeは安定してないようですね。
ソート前時点での並び順を覚えておいて判定する方法で安定したソートにしてみたいと思います！

[Meganezaru]

jQuery.fn.sortを置き換えるのは、なんとなく危険(笑)な気がしたので、別名称のprototypeで安定ソートを実装し、問題なく動作しました。

みなさま、ありがとうございました！

Answer 2

そもそも、jQueryの要素は（同一ドキュメントから拾った場合）ドキュメント内での順番と同じ順番に並ぶことになっていますので（.addのドキュメント）、手動でのソート機能はありません。

jQueryのリファレンスを確認しましたが、$().sort()というメソッドは標準では用意されていません。

Comments

[Meganezaru]

早速のご回答ありがとうございます！

たしかにjQueryのリファレンスで、sort()は見つからないですね(；´∀｀)

上のコードが動作するのであれば、children（自分で試した時は、findを使いましたが・・・）で取得した結果が、Arrayになるということでしょうか？

[maisumakun]

.childrenの結果もjQueryオブジェクトのはずなので、どこかで何かしらのライブラリやコードが$.fn.sortをセットしている、ということでしょう。

[Meganezaru]

なるほど！

$.fn.sortをセットしているライブラリを探して、そのライブラリのリファレンスか実装を見る必要があるということですね。

参考になりました！ありがとうございます！

[Lhankor_Mhy]

横からすみません。
気になってjQueyのソースコード読んでみましたが、jQueryオブジェクトは基本的にArrayLikeなので、普通にsortメソッド効きそうですね。
よく考えるとインデクシングができるわけですから、まあ当然と言えば当然ですよね。

[Meganezaru]

@Lhankor_Mhy さん

コメントとｊQueryのソース確認ありがとうございます！

私も、ちょっとjQueryのソースを眺めてました。
どうやら、core.jsで、jQuery.fn.sortにArrayのソートをセットしているようでしたので、まずは、jQuery.fn.sortを安定ソートできる処理に置き換えて試してみようと思います。

[Lhankor_Mhy]

ああ、そうでしたか。そうですよね、ArrayLikeでもメソッドが付いてくるわけじゃないですよね。
横から口を挟んだ上に間違えてすみませんでした。

[Meganezaru]

@Lhankor_Mhy さん

いえいえ、確認していただいてありがたかったです。
jQueryソースを見てみるという行動にもつながりましたし！