Может ли измененная быстрая сортировка быть O (n) лучшим случаем?

Question

Общепринято, что лучшим вариантом быстрой сортировки является O (nlogn), учитывая, что массив разбивается примерно наполовину каждый раз.Также сказано, что наихудший случай порядка n ^ 2, при условии, что массив отсортирован.

Разве мы не можем изменить быструю сортировку, установив логическое значение, называемое swap?Например, если для первого прохода не существует начального свопинга в позиции, мы можем предположить, что массив уже отсортирован, поэтому не делим данные дальше.

Я знаю, что модифицированная пузырьковая сортировка использует это, проверяя наличие перестановок, позволяя в лучшем случае быть O (n), а не O (n ^ 2).Можно ли применить этот метод к быстрой сортировке?Почему или почему нет?

Answer 1

В вашем подходе есть одна ошибка ... Например, у нас есть такой массив: 1243 5 678

наш элемент Pivot равен 5. После первого прохода не будет свопа (потому что 4 и3 меньше), но массив НЕ отсортирован.Таким образом, вы должны начать делить его, и это приводит к п журнала п.

Answer 2

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

Answer 3

Кроме того, также существует проблема, связанная с тем, что вы также получаете поведение O (n) с почти отсортированными массивами в дополнение к полностью отсортированному входу.

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