Я узнаю о быстрой сортировке и хочу проиллюстрировать различные массивы, для которых быстрой сортировке будет сложно. Имеющаяся в виду быстрая сортировка не имеет начального случайного перемешивания, делает 2 разбиения и не вычисляет медиану.
До сих пор я придумал три примера:
[1,2,3,4,5,6,7,8,9,10] - when the array is sorted
[10,9,8,7,6,5,4,3,2,1] - when the array is reversed
[1,1,1,1,1,1,1,1,1,1] - when the array is the same values
[1,1,1,2,2,2,3,3,3,3] - when there are few and unique keys
Например, я не слишком уверен в этом:
[1,3,5,7,9,10,8,6,4,2]
Так что же делает массив с быстрой сортировкой по сравнению с тем, где он (почти) идеален?
algorithms
sorting
mrQWERTY
источник
источник
[2,1,2,1,2,1,2,1]и это в целом ответ). В идеале целью этого вопроса будет то, куда другие люди могут прийти и узнать больше о причинах (у которых есть ответ), а не о примерах (которых существует бесчисленное множество).Ответы:
Каждый алгоритм сортировки имеет наихудший случай, а во многих случаях наихудший случай действительно плохой, поэтому его стоит проверить. Проблема в том, что не существует ни одного худшего случая только потому, что вы знаете основной алгоритм.
Распространенные наихудшие случаи: уже отсортированы; отсортировано в обратном порядке; почти отсортирован, один элемент не в порядке; все значения одинаковы; все равно кроме первого (или последнего) выше (или ниже). Когда-то у нас был такой случай, когда наихудшим случаем был конкретный пилообразный паттерн, который было очень трудно предсказать, но довольно распространенный на практике.
Наихудший случай для быстрой сортировки - тот, который заставляет ее всегда выбирать наихудший возможный круг, так что один из разделов имеет только один элемент. Если pivot - это первый элемент (неправильный выбор), то худшие случаи - это уже отсортированные или обратно отсортированные данные. Для медианы из трех сводных данных, которые все одинаковы или только первое или последнее отличается, делает трюк.
Для быстрой сортировки средняя сложность равна nlogn, а худший - n ^ 2. Причина, по которой стоит вызывать поведение в худшем случае, заключается в том, что это также тот случай, который дает наибольшую глубину рекурсии. Для простой реализации глубина рекурсии может быть n, что может вызвать переполнение стека. Тестирование других экстремальных ситуаций (в том числе в лучшем случае) может оказаться целесообразным по аналогичным причинам.
источник
O(NlogN)производительностью или лучше) худшие и средние случаи имеют одинаковую сложность. Это говорит о том, что обычно не стоит тестировать наихудшие случаи. (Учитывая, что тест, вероятно,O(N)... или хуже.)Алгоритм выходит из большинства плохих случаев с использованием рандомизированной сводки, исключающей непрерывные элементы, равные сводке от разбиения, и асимметричного поиска. Он ищет элемент больше или равен точке поворота и ищет элемент назад меньше точки поворота.
Я благодарю MichaelT, Асимметричный поиск разработан для разрешения [2,1,2,1,2,1,2,1].
Следующий результат генерируется моей функцией qsort_random (). N = 100 000
Большинство случаев быстрее, чем случайный образец. Схема долины - плохой случай для большинства опорных точек.
qsort_log2 () выходит из плохого случая, выбирая стержень в элементах log2 (N).
qsort (3) использует библиотеку GNU, которая является сортировкой индекса слиянием.
qsort_trad () выбирает стержень в первом, среднем и последнем элементах.
qsort_random () и qsort_log2 () не используют обмен.
Программы и скрипты Source C размещены на github .
источник