Qucksort 3way призван помочь случаю, когда много/большинство элементов массива равны.Будет ли `quicksort 3way` медленнее, чем` quicksort` в общем случае?
Мой вопрос: Будет ли quicksort 3way бьет quicksort в общем случае?
по общему случаю, я имею в виду, что не много предметов равны или больше, все элементы различны.
Я сделал несколько тестов, и я чувствую, что в общем случае quicksort 3way еще хуже, чем классический quicksort.
Дайте немного подумать: у вас есть алгоритм, разработанный, чтобы помочь вам решить худший сценарий для другого алгоритма. Конечно, в общем случае он не должен бить исходный алгоритм. Идея в 3-х мерном хозяйстве - это улучшение поведения худшего случая, а не среднего случая.
Я думаю, что ваш ответ слишком высокий, не так ли? Я здесь фактически действую, почему, а не логическая причина высокого уровня. –
. Вы не указали никаких подробностей о ваших конкретных реализациях. Я не могу дать более подробный ответ таким образом. Обратите внимание на это предложение из вашей ссылки: «3-полосный код разбивки, показанный выше, написан для ясности, а не для оптимальной производительности; он демонстрирует плохую локальность и выполняет больше свопов, чем необходимо. ' –
На это можно ответить более точное определение «общего случая». Почему бы не попробовать? – madth3