Сложность быстрой сортировки, когда все элементы одинаковы?

Question

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

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

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

Answer 1

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

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

Answer 2

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

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

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

Answer 3

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

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

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

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

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

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

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

Answer 4

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

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

Обмен кодом из princeton

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

Answer 5

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