boobymayton,

Потерпи меня еще минуту.
Еще одно замечание, касательное специальных собственных характеристик алгоритмов сортировки, может быть полезных в специальных частных случаях.

Вот пирамидальная сортировка, которой ты формально посвятил тему:
неустойчива, так же как и быстрая
- для "среднего случая" оценивается как несколько хуже быстрой при той же асимптотике.

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

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

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

Не могли бы вы пожалуйста привести пример так называемых вами специальных статических случаев?)

boobymayton,


Вот пирамидальная сортировка, которой ты формально посвятил тему:
- неустойчива, так же как и быстрая
- для "среднего случая" оценивается как несколько хуже быстрой при той же асимптотике.

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


Это скорее не сортировка с использование структуры данных, в сортировка основанная на использование удачной структуры данных. В данном конкретном случае, исторически есть смысл ссылаться на сортировку выбором и оптимизацию выбора нового минимального элемента не за счет поиска по всему массиву за O(n) итераций, использование удачной структуры данных и дает нам в итоге(это ключевые слова) O(lgn) на поиск нового элемента. Потому это сортировка появившаяся только благодаря удачной и красивейшей структуре данных - пирамиды.

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

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


Я понимаю то, о чем говорил White Owl - действительно, существуют различные вариации пирамидальной сортировки и т.д. и т.п. Но то, о чем говорите вы, мне не очень понятно. Если вас это не слишком затруднит, приведите пожалуйста конкретный набор данных, конкретную серию и какая именно сортировка выполняется. Возможно вы имеете что-то другое, и я вас просто не понимаю, поскольку у пирамидальной сортировки в классическом понимании есть хорошая оценка асимптотики независимо от каких либо случаев: "худший", "лучший","средний".