Introselect

В информатике, introselect (сокращение от «интроспективный выбор») - это алгоритм выбора, который представляет собой гибрид quickselect и медианы медиан который имеет высокую среднюю производительность и оптимальную производительность в худшем случае. Introselect относится к алгоритму сортировки introsort : это аналогичные уточнения базовых алгоритмов quickselect и quicksort, поскольку оба они начинаются с быстрого алгоритма, который имеет хорошую среднюю производительность и низкие накладные расходы, но возвращается к оптимальному алгоритму наихудшего случая (с более высокими накладными расходами), если быстрый алгоритм не развивается достаточно быстро. Оба алгоритма были представлены Дэвидом Массером в (Musser 1997) с целью предоставления общих алгоритмов для стандартной библиотеки C ++, которая имеют как высокую среднюю производительность, так и оптимальную производительность в худшем случае, что позволяет ужесточить требования к производительности. Однако в большинстве реализаций стандартной библиотеки C ++, которые используют introselect, используется другой алгоритм «introselect», который сочетает в себе quickselect и heapselect и имеет время работы O (n log n) в худшем случае.

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

Introselect работает оптимистично, начиная с быстрого выбора и переключаясь только на алгоритм линейного выбора наихудшего случая (алгоритм Блюма-Флойда-Пратта-Ривеста-Тарьяна медиана медиан ), если он повторяется слишком много раз без достаточного прогресса. Стратегия переключения - это основное техническое содержание алгоритма. Недостаточно просто ограничить рекурсию постоянной глубиной, так как это заставит алгоритм переключаться на все достаточно большие списки. Муссер обсуждает несколько простых подходов:

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

Оба подхода ограничивают глубину рекурсии до k ⌈log n⌈ = O (log n), а общее время выполнения - до O (n).

В документе говорилось о предстоящих новых исследованиях интроселекта, но автор ушел на пенсию в 2007 году, не опубликовав никаких подобных исследований.

• алгоритм Флойда – Ривеста