ソートアルゴリズムはNSArrayの安定したソートで使用されていますか？

Question

NSArrayのさまざまなソート方法でソートアルゴリズムを使用していますか？ （同じソートキーを持つアイテムの相対的な順序が保存されている「安定ソート」アルゴリズムの場合と同じです。）

Answer 1

docには、同じ項目の最終的な順序についての詳細は記載されていません。

したがって、私は順序が悪い考えであると仮定していると感じます。実験的に何を決定したとしても、配列内の項目数やiOSのどのバージョンがソートを実行するかによって変わる可能性があります。

私にとって、私はドキュメントによって提供される約束に固執します。

Answer 2

私はこれについて見つけた唯一の「公式」の答えは、Appleからのクリス・ケインによって2002 mailing list postです：

にNSArray/NSMutableArrayののソート方法の安定性が定義されていない、 ので、あなたは、彼らがあることを予想しなければなりません不安定です。定義されていないので、 の状況もリリースごとに変更される可能性がありますが、私は （自分自身）はこれがそうであると予想しています。現在の実装 は、BSDの qsort（）ルーチンとほぼ同じアルゴリズムのバージョンであるクイックソートを使用しています。 1つの点でそれが のデータの一般的なタイプのそれよりもうまくいくのは難しいと私たちは を通してテストで見つけた一連の実験。 [1は、ソー​​トされたデータについての追加情報 を持っている場合はもちろん、一方が他方のアルゴリズムまたはそのケースを助ける 修正を使用することができます。]

私はこれが何歳を考えると、まだ本当であるかどうかわかりません投稿はありますが、おそらくNSArrayのソート方法はではなく、であると仮定するのが最善です。

Answer 3

NSSortStableを使用しない限り、安定した並べ替えは保証されません。 documentation on NSSortOptionsから：

NSSortStable

ソート結果が比較項目は、彼らが最初に発生した順に等しい値を持って返すことを指定します。

このオプションが指定されていない場合、等しいオブジェクトが元の順序で返されることもあれば返されないこともあります。あなたが安定したソートを保証する必要がある場合は

することは、何かしてみてください：

[array sortWithOptions:NSSortStable usingComparator:^NSComparisonResult(id obj1, id obj2) { 
    return [obj1 compare:obj2]; 
}];