Пример лучшего сценария для быстрой сортировки (нужен кто-то, чтобы проверить, верен ли мой ответ)

Question

Используя список из 15 чисел, мне нужно дать список, представляющий лучший и худший сценарий. Там написано: «q.s. использует первый элемент в списке в качестве основного элемента». Я не уверен, что каждый раз выбираю первый элемент как опорный, но это то, что я предполагаю ....

В лучшем случае ... Я придумал (жирный шрифт, курсив для маркеров больше и меньше):

8 1 3 2 6 5 7 4 12 9 11 10 14 13 15

4 1 3 2 6 5 7--8 - 12 9 11 10 14 13 15

2 1 3 --4 - 6 5 7 ...... ..8 ........ 10 9 11--12--14 13 15

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Надеюсь, что кто-то может здесь проверить мою работу, и если это не так, укажите мне, как и почему.

Answer 1

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

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

Еще один метод - это поставить стержень в первый слот до его размещения и поменять его местами с последним, не превышающим шарнир после.

В лучшем случае для этих стратегий требуются разные конфигурации. Например,

4 1 3 5 6 7 2

- лучший вариант для варианта «поменять местами в последнем месте», в то время как

4 1 3 2 6 5 7

- лучший вариант для «Pivot Stays Put».

Наихудший сценарий - когда сводная точка всегда переходит к одному из концов массива, точные детали снова зависят от реализации, но сортировка или обратная сортировка обычно являются наихудшими случаями.

Answer 2

Это выглядит правильно для меня.Если вы используете быструю сортировку с первым элементом в качестве оси, то вы хотите, чтобы первый элемент был средним значением массива.Идеальный круг имеет равномерное количество элементов на каждой стороне.