QuickSort Partitioning Pivot Anomaly

Question

Рассмотрим массив A = {1,2,0,4,5}, как мне отсортировать это, используя быструю сортировку, взяв средний элемент в качестве центра в процессе разделения? .. Элемент становится «0» и так в в этом массиве нет действительного левого указателя. Как решить эту аномалию? Кто-нибудь может объяснить мне пошаговую работу этого алгоритма?

Answer 1

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

A медиана медиан , которые разделяют элементы между 30% / 70% и 70% / 30%, таким образом всегда гарантируя минимальный прогресс 30%, хорошая статья , объясняющая это, которое недавно (2017) было улучшено Александреску и др. с помощью адаптивного алгоритма.