Быстрая сортировка, когда все элементы одинаковы?

Ответ 1

Это зависит от реализации Quicksort. Традиционная реализация, которая разбивается на секции 2 (< и >=), будет иметь O(n*n) на одинаковом входе. В то время как без свопов обязательно произойдет, это вызовет рекурсивные вызовы n, каждый из которых должен провести сравнение с элементами pivot и n-recursionDepth. то есть O(n*n) должны быть сделаны сравнения

Однако существует простой вариант, который разбивается на 3 набора (<, = и >). В этом случае этот вариант имеет производительность O(n) - вместо выбора поворота, замены и последующего рекурсии на 0 до pivotIndex-1 и pivotIndex+1 до n, он поместит все вещи равными оси вращения на "средний" раздел (который в случае всех идентичных входов всегда означает "свопинг с самим собой", то есть без-op), что означает, что стек вызовов будет только 1 глубже в этом конкретном случае n сравнений и без свопов. Я считаю, что этот вариант пробился в стандартную библиотеку по Linux по крайней мере.

Ответ 2

Производительность быстрой сортировки зависит от выбора поворота. Чем ближе выбранный стержень к медианному элементу, тем лучше производительность quicksort.

В этом конкретном случае вам повезло - выбранный вами центр всегда будет медианным, поскольку все значения одинаковы. Таким образом, этап разделения quicksort никогда не будет заменен элементами, и два указателя будут встречаться ровно посередине. Таким образом, две подзадачи будут иметь ровно половину размера - это даст вам идеальный O(n log n).

Чтобы быть более конкретным, это зависит от того, насколько хорошо реализован шаг раздела. Инвариант цикла должен только убедиться, что меньшие элементы находятся в левой подзадаче, в то время как большие элементы находятся в правой подзадаче. Там нет гарантии, что реализация раздела никогда не заменяет равные элементы. Но это всегда ненужная работа, поэтому никакая умная реализация не должна делать этого: указатели left и right никогда не обнаружат инверсию, соответствующую оси вращения (т.е. Вы никогда не столкнетесь с случаем, когда *left > pivot && *right < pivot), и поэтому left указатель будет увеличен, указатель right будет уменьшаться на каждом шаге и, наконец, встретится посередине, создавая подзадачи размера n/2.

Ответ 3

Это зависит от конкретной реализации.

Если существует только один вид сравнения (≤ или <), чтобы определить, куда будут перемещаться другие элементы относительно оси, все они войдут в один из разделов, и вы получите O (n ²), так как размер проблемы будет уменьшаться всего на 1 шаг.

Ниже приведен пример алгоритма приведенный здесь (сопроводительная иллюстрация для другого алгоритма).

Если имеется два вида сравнений, например, < для элементов слева и > для элементов справа, как это имеет место в реализации с двумя указателями, и если вы позаботитесь перемещать указатели в шаге, то вы можете получить отличную производительность O (n log n), потому что половина равномерных элементов будет разделяться равномерно в двух разделах.

В приведенных выше ссылках используется алгоритм, который не перемещает указатели на шаге, поэтому вы по-прежнему получаете низкую производительность (посмотрите на "Немного уникальных" случаев).

Итак, это зависит от того, имеете ли вы этот особый случай при реализации алгоритма.

Практические реализации часто обрабатывают более широкий частный случай: если на этапе разбиения нет свопов, они предполагают, что данные почти отсортированы и используют сортировку вставки, что дает еще лучший O (n) в случае всех равные элементы.

Ответ 4

tobyodavies предоставили правильное решение. Он обрабатывает регистр и заканчивается в O (n) раз, когда все ключи равны. Это то же самое разделение, что и в проблеме голландского национального флага

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

Совместное использование кода из принтэтона

http://algs4.cs.princeton.edu/23quicksort/Quick3way.java.html

Ответ 5

Если вы реализуете двухсторонний алгоритм секционирования, то на каждом шаге массив будет уменьшен вдвое. Это связано с тем, что при обнаружении идентичных ключей сканирование прекращается. В результате на каждом шаге элемент разбиения будет располагаться в центре подмассива, тем самым уменьшая вдвое количество массива в каждом последующем рекурсивном вызове. Теперь этот случай похож на случай mergesort, который использует ~N lg N, сравнивает сортировку массива из N элементов. Ergo для дубликатов ключей, традиционный алгоритм двухпоточного секционирования для Quicksort использует ~N lg N, сравнивая, тем самым следуя линейно-лимитическому подходу.