Являются ли алгоритмы сортировки используемыми стабильными сортами NSArray?

Question

Являются ли алгоритмы сортировки, используемые различными методами сортировки в NSArray stable? (Как и в случае, они являются алгоритмами «стабильного сортирования», когда элементы с таким же ключом сортировки сохраняют относительные порядки.)

Answer 1

В doc подробных данных об окончательном заказе одинаковых предметов не приводится.

Поэтому я считаю, что любые предположения о заказе были бы плохими идеями. Даже если вы экспериментально определите, что такое заказ, это может измениться в зависимости от количества элементов в массиве или какой версии iOS выполняет сортировку.

Для меня я придерживался обещаний, предоставленных документацией.

Answer 2

только «официальный» ответ, который я нашел про это 2002 mailing list post Крис Кейн от компании Apple:

Устойчивость методов сортировки NSArray/NSMutableArray является неопределенным, поэтому следует ожидать, что они неустойчиво. Будучи неопределенным, ситуация может также измениться с момента выпуска на выпуск, хотя я не (я) ожидаю, что это вероятно. Текущая реализация использует быструю сортировку, версию алгоритма, почти идентичную процедуре qsort() BSD qsort(). Несколько экспериментов, найденных в какой-то момент, что было трудно сделать лучше, чем для общих типов данных, мы провели на тестах. [Конечно, если у Вас есть дополнительная информация о данных, отсортированных, можно использовать другие алгоритмы или модификации, которые помогают тот случай.]

Я не знаю, является ли это все еще верно, учитывая, сколько лет пост, но, вероятно, лучше всего предположить, что методы сортировки NSArray: не стабильный.

Answer 3

Стабильный сорт не гарантируется, если вы не используете NSSortStable. Из documentation on NSSortOptions:

NSSortStable

Указывает, что отсортированные результаты должны вернуть по сравнению элементы имеют одинаковое значение в порядке их возникновения первоначально.

Если этот параметр не указан, равные объекты могут быть возвращены или не возвращены в исходном порядке.

Если вам нужно, чтобы гарантировать стабильную сортировку, попробовать что-то вроде:

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