Быстрая сортировка: выбор точки

Question

При реализации быстрой сортировки одна из вещей, которую вам нужно сделать, это выбрать опору. Но когда я смотрю на псевдокод, подобный приведенному ниже, неясно, как мне выбрать пивот. Первый элемент списка? Что-то еще?

 function quicksort(array)
     var list less, greater
     if length(array) ≤ 1  
         return array  
     select and remove a pivot value pivot from array
     for each x in array
         if x ≤ pivot then append x to less
         else append x to greater
     return concatenate(quicksort(less), pivot, quicksort(greater))

Может ли кто-нибудь помочь мне понять концепцию выбора пивота и определить, требуют ли разные сценарии разные стратегии.

Answer 1

Сложность быстрой сортировки сильно зависит от выбора значения разворота. например, если вы всегда выбираете первый элемент как опорный, сложность алгоритма становится такой же худшей, как O (n ^ 2). Вот умный способ выбрать элемент 1. выберите первый, средний, последний элемент массива. 2. сравните эти три числа и найдите число, которое больше единицы и меньше, чем другие, то есть медиана. 3. сделать этот элемент как элемент поворота.

выбор оси этим методом делит массив почти на две половины и, следовательно, сложность сводится к O (nlog (n)).

Answer 2

В действительно оптимизированной реализации метод выбора сводки должен зависеть от размера массива - для большого массива стоит потратить больше времени на выбор хорошей сводки. Без полного анализа я бы предположил, что «середина O (log (n)) элементов» - это хорошее начало, и это дает дополнительный бонус - не требует дополнительной памяти: использование tail-call на большем разделе и размещая разделы, мы используем одну и ту же O (log (n)) дополнительную память практически на каждом этапе алгоритма.

Answer 3

В идеале ось должна быть средним значением во всем массиве. Это уменьшит шансы получить худшую производительность.