Я пытаюсь понять, почему быстрая сортировка с использованием раздела Lomuto и фиксированной точки вращения работает хаотично, но в целом плохо, на случайно сгенерированных входах. Я думаю, что, хотя входы генерируются случайным образом, последовательности могут иметь много порядка, но я не уверен, как измерить уровень беспорядка в последовательностях. Я думал об использовании числа инверсий, но из этого другого вопроса я увидел , что в данном случае это не очень хорошая мера.
Причина, по которой я подозреваю, что мои случайные последовательности имеют много «порядка», заключается в том, что рандомизация сводки решает проблему производительности. Но теоретически не должно быть никаких проблем с производительностью этих предположительно «случайных» входных последовательностей.
источник
Ответы:
Lomuto vs Hoare
Раздел Lomuto страдает при сортировке равных ключей, тогда как раздел Hoare - нет.
Обе схемы разбиения страдают одинаково при использовании оси, удаленной от медианы.
Мера беспорядка
Мера беспорядка, чтобы выбрать для целей быстрой сортировки, проста.
A: Насколько далеко от медианы находится фиксированный опорный пункт по сравнению со случайными данными?
Если вы настаиваете на использовании раздела Lomuto и предполагаете, что дублирующиеся значения разрешены, вам нужно добавить следующий тест на случайность:
B: Сколько существует дублирующих элементов по сравнению со случайным.
Конечно, довольно глупо предполагать, что в вашем наборе данных разрешены повторяющиеся значения, и при этом оценивать раздел Lomuto, поэтому вам, вероятно, следует либо удалить дубликаты заранее, либо переключиться на раздел Hoare, либо предположить, что дубликаты встречаются редко.
Обе меры тривиальны для количественной оценки с использованием статистики.
Мы можем исключить патологические данные.
Любые другие отклонения от случайности не будут иметь значения для анализа быстрой сортировки. Пока ось близка к медиане, она будет хорошо работать на всех данных, которые не являются патологическими.
Расстояние от случайного должно быть действительно большим, чтобы быть быстродействующим патологическим, поэтому мы можем исключить это.
Никогда не используйте какие-либо фиксированные точки в реальном коде.
Обратите внимание, что если вы пишете реальный код с фиксированной точкой *) (какой бы она ни была), вы открываете себя для атаки типа «отказ в обслуживании», потому что злоумышленник может вставить патологическое значение именно в этой точке, и поэтому вы должны всегда выбирать случайный элемент в качестве точки разворота.
*) или несколько пивотов, если вы выбираете лучший из х пивотов.
источник