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

У меня есть массив из N чисел, которые одинаковы. Я использую Quick sort на нем. Какова должна быть временная сложность сортировки в этом случае.

Я изучил этот вопрос, но не получил точного объяснения.

Любая помощь будет оценена по достоинству.

    Это зависит от реализации 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.

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

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

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

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

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

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

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

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

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

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

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

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

    Обмен кодом с принтэтона

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

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