Есть ли метод черного ящика, чтобы определить, стабилен ли алгоритм сортировки?

В JavaScript (несколько применимом в другом месте), где вы не знаете, в какую целевую реализацию работает ваш код, существует ли способ распознавания, если базовый алгоритм сортировки (Array.sort) стабилен или нет, зная только что следует спецификация?

Я мог бы найти 2 теста в webkit (1) ( 2), но насколько надежны эти тесты? (Может ли эта проверка быть выполнена с помощью PCP?) Я ищу решение, которое было бы математически звуковым.

Это сложная проблема, поскольку более продвинутый алгоритм сортировки может изменять субалгоритмы в зависимости от длины исходного массива (например, Timsort). Я был сбит с толку, так как каждый прогон, который я выполнил, показал, что сортировка Google Chrome стабильна, но вся документация, которую я видел, сказала, что она неустойчива (источник сообщит вам, почему).

(Как правило, я использую эту стратегию, чтобы сделать мой ролик стабильным, он имеет небольшое, но иногда заметное влияние на производительность)

Исходный код для сортировки в различных реализациях:

Ответ 1

Тестирование Black-box не может использоваться для определения того, что программа удовлетворяет любому критерию, если вы не можете проверить все возможные входные данные, относящиеся к критерию. Черному ящику можно просто иметь таблицу поиска, которая отображает входные данные для выходов (см. ошибка Pentium FDIV для ошибки в реальном мире таблицы поиска), поэтому вы не можете быть уверены, что ваши тесты исключают возможность того, что какой-либо другой вход вызывает нарушение.

Ответ 2

Математически звучит, а? Это потребовало бы, чтобы каждый путь в алгоритме считался стабильным - и каждой их комбинацией. Для любых возможных данных.

Конечно, такие алгоритмы существуют, но они, скорее всего, были сделаны в соответствии с этим требованием. Так что, если это так, вероятно, он говорит, что это где-то.

Что касается теста, чтобы доказать что-то подобное, это, вероятно, относится к аналогичным проблемам, как проблема с остановкой.

http://en.wikipedia.org/wiki/Halting_problem

Ответ 3

Зачем рисковать? Для большинства разумных наборов данных реализация jayscript слияния должна быть достаточно быстрой. Возьмите пару и сравните их и используйте лучший.

Ответ 4

Запустите небольшой внутренний тест, чтобы проверить? Вы можете использовать пример "игральные карты по рангу, затем по костюмам" из Википедии, чтобы проверить стабильность.

Смотрите: https://en.wikipedia.org/wiki/Sorting_algorithm#Stability

Я не знаю, сколько карточек вам нужно для проверки стабильности - возможно, 5 или около того?