NSArrayではどのようなソート関数が使用されていますか？

Question

これは本当に3つの質問ですが、私は最初の質問に自分自身で答えました。

私はiPhone上で、多くのオブジェクト（最大200個）を画面に表示しています。各オブジェクトは、他のオブジェクトと重なっているかどうかを調べ、それに応じて動作する必要があります。私の元々素朴な実装では、オブジェクトごとにオブジェクトのリストを実行して境界ボックスを確認しました（​​を使用）。

私の質問（および回答）は、よりよい方法です。私の新しい実装では、各オブジェクトのy位置に挿入ソート（データは大部分が既にソートされているので）を使用して各フレームを並べ替えることです。次に、最も近いオブジェクトのみを検索して、それは垂直に範囲内にあり、次に水平にチェックします。

最初の質問：挿入は、ランダムに動き回る傾向がありますが、ほとんどの場合、最後のフレームに基づいて順序を維持する傾向があるオブジェクトの配列に使用する方法をソートしていますか？また：私はそれが一般的なケースで最も有用なので、私は一種の、それはクイックソートを使用することを前提としています

- sortedArrayUsingSelector: 

を呼び出したときにどのようなアルゴリズムにNSArrayを使うん。誰かが私が間違っているかどうか知っていますか？私はソート方法を変更することができますか、または私は自分のソート機能を記述する必要がある場合は誰も知っていますか？

2番目の質問：むしろ、私は

- indexOfObject: 

で使用されていると仮定したり、私は自分自身を記述する必要があります単純な手法よりも、バイナリ検索を使用してソートされた配列から項目を取得するための機能がありますか？

Answer 1

NSArrayは、配列に含まれるオブジェクトの数に応じて、さまざまなデータ構造を内部的に使用します。詳細は、Peter Ammon blog entryを参照してください。しかし基本的には、ある種の並べ替えが起こるとは期待できません。場合によっては、C配列を使用して独自の配列実装を作成して、ソートを自分で制御できるようにする価値があります。

衝突検出を実装する方法がはるかに高速です。 KDツリーやそれに類するものなどのバウンディングボリューム階層を調べてください。

私が知っている限り、indexOfObject：は唯一の方法ですが、潜在的にあなたが思っているほど馬鹿ではありません。すべてNSDictionaryのためにハッシュ可能なので、NSArrayでそれらのスマートのいくつかを使用することができます。