NSArray에서 사용되는 정렬 함수는 무엇입니까?

Question

이것은 실제로 세 부분으로 구성된 질문이지만 처음 질문에 직접 대답했습니다.

저는 iPhone에서 작업 중이며 화면에는 많은 개체 (최대 200 개)가 있습니다. 각 객체는 다른 객체가 겹쳐져 있는지 살펴야합니다. 원래 원래 구현은 각 객체가 각 객체의 목록을 통해 경계 상자를 확인하기 위해 실행하는 것입니다 (CGRectInsersectsRect 사용).

제 질문 (답변)이 더 좋은 방법입니까? 내 새로운 구현은 각 객체의 y 위치에 삽입 정렬을 사용하여 배열을 정렬하고 (데이터가 대부분 정렬되어 있으므로), 가장 가까운 객체 만 검색하여 범위가 수직이며 수평으로 확인하십시오.

첫 번째 질문 : 삽입은 무작위로 이동하는 경향이있는 객체 배열에 대해 사용하려는 메서드를 정렬하지만 대부분 마지막 프레임을 기반으로 순서대로 머물러 있지 않으므로 약간 삽입해야합니까? 또한 : 나는

- sortedArrayUsingSelector: 

를 호출 할 때 NSArray를 사용 않습니다 어떤 종류의 알고리즘 나는 종류는 일반적인 경우에 가장 유용 이후는 빠른 종류를 사용한다고 가정합니다. 아무도 내가 틀렸다는 것을 알고 있습니까? 아무도 내가 정렬 메서드를 변경할 수 또는 만약 내가 내 자신의 정렬 함수를 작성해야 알 수 있습니까?

두 번째 질문 : 오히려 내가

- indexOfObject: 

에서 사용하는 가정 또는 내가 내 자신을 작성해야 순진한 접근보다, 이진 검색을 사용하여 정렬 된 배열에서 항목을 검색하는 기능이있다?

Answer 1

NSArray는 배열에 몇 개의 객체가 있는지에 따라 내부적으로 많은 다른 데이터 구조를 사용합니다. 자세한 내용은 Peter Ammon blog entry을 참조하십시오. 그러나 기본적으로 이것은 어떤 종류의 일이 일어날 것을 기대할 수 없다는 것을 의미합니다. 때로는 C 배열을 사용하여 배열 구현을 작성하여 직접 정렬을 제어 할 가치가 있습니다.

확실히 빠른 충돌 탐지를 구현하는 방법이 있습니다. KD 나무 또는 유사 물과 같은 경계 체적 계층을 조사하십시오.

필자가 아는 한 indexOfObject : 유일한 방법이지만 생각만큼 바보 같지는 않습니다. 모든 NSDictionary에 대한 해시 가능하므로 NSArray에서 해당 스마트 중 일부를 사용할 수 있습니다.