Блог компании OTUS. Онлайн-образование
Алгоритмы
Комментарии 6
+3

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

0
Полезная статья! Очень полезная! Очень очень полезная! Но как по мне слишком большой порог вхождения, можно сначала пузырьковую сортировку на всех языках мира?
0
Я понимаю, что это всего лишь перевод статьи с geeksforgeeks (образовательные статьи с geeksforgeeks?) по очень избитой теме, но перевести ведь можно и получше, есть ведь какая-то общепринятая терминология в русском языке.

1. «Законченное двоичное дерево».
Возможно, этот термин где-нибудь и применяется, но обычно это либо называют «полным двоичным деревом», либо вообще никак не называют, описывая правила построения

2. «Пирамидальная сортировка — это вполне годный алгоритм. Его типичная реализация не стабильна, но может быть таковой сделана».
Не стабильна, близка к распаду. Вроде бы обычно в русском языке термин «stable sort» называют «устойчивой сортировкой».

3. Описание алгоритма.
«Наконец, преобразуйте полученное дерево в max-heap с новым корнем.».
В оригинале ведь все куда более конкретно: «Finally, heapify the root of tree.» и затем идет описание того, что же такое «heapify». В переводе термин «heapify» потерян, из-за этого логика становится куда более размытой.
Также третий пункт описания алгоритма «Повторяйте вышеуказанные шаги, пока размер кучи больше 1.» в оригинале написан неудачно (не очень понятно. нужно повторять шаги 1 и 2 или только 2), и тут также оставлен без изменений (причем русскоязычный вариант субъективно еще менее понятный).
В результате по описанию этого простого алгоритма, на мой взгляд, вообще мало что понятно без чтения кода или дополнительного поиска информации (что возвращает нас к теме качества статей на geeksforgeeks).
+1
Его типичная реализация не стабильна, но может быть таковой сделана (см. Здесь).

Так себе решение. Для достижения стабильности потребуется O(n) памяти и еще больше просадит производительность. Скорее всего получится хуже по всем параметрам, чем merge sort.
Идеального алгоритмя до сих пор нет (гарантированая сложность O(n * log n), константа (или хотя бы логарифм) по памяти, стабильность).

Только полноправные пользователи могут оставлять комментарии.  , пожалуйста.