Комментарии 6
Изящный алгоритм с хорошими гарантиями производительности, когда изучил впервые, был очень впечатлён.
Полезная статья! Очень полезная! Очень очень полезная! Но как по мне слишком большой порог вхождения, можно сначала пузырьковую сортировку на всех языках мира?
Спасибо, нам нужно больше копипасты с гитхаба.
Я понимаю, что это всего лишь перевод статьи с geeksforgeeks (образовательные статьи с geeksforgeeks?) по очень избитой теме, но перевести ведь можно и получше, есть ведь какая-то общепринятая терминология в русском языке.
1. «Законченное двоичное дерево».
Возможно, этот термин где-нибудь и применяется, но обычно это либо называют «полным двоичным деревом», либо вообще никак не называют, описывая правила построения
2. «Пирамидальная сортировка — это вполне годный алгоритм. Его типичная реализация не стабильна, но может быть таковой сделана».
Не стабильна, близка к распаду. Вроде бы обычно в русском языке термин «stable sort» называют «устойчивой сортировкой».
3. Описание алгоритма.
«Наконец, преобразуйте полученное дерево в max-heap с новым корнем.».
В оригинале ведь все куда более конкретно: «Finally, heapify the root of tree.» и затем идет описание того, что же такое «heapify». В переводе термин «heapify» потерян, из-за этого логика становится куда более размытой.
Также третий пункт описания алгоритма «Повторяйте вышеуказанные шаги, пока размер кучи больше 1.» в оригинале написан неудачно (не очень понятно. нужно повторять шаги 1 и 2 или только 2), и тут также оставлен без изменений (причем русскоязычный вариант субъективно еще менее понятный).
В результате по описанию этого простого алгоритма, на мой взгляд, вообще мало что понятно без чтения кода или дополнительного поиска информации (что возвращает нас к теме качества статей на geeksforgeeks).
1. «Законченное двоичное дерево».
Возможно, этот термин где-нибудь и применяется, но обычно это либо называют «полным двоичным деревом», либо вообще никак не называют, описывая правила построения
2. «Пирамидальная сортировка — это вполне годный алгоритм. Его типичная реализация не стабильна, но может быть таковой сделана».
Не стабильна, близка к распаду. Вроде бы обычно в русском языке термин «stable sort» называют «устойчивой сортировкой».
3. Описание алгоритма.
«Наконец, преобразуйте полученное дерево в max-heap с новым корнем.».
В оригинале ведь все куда более конкретно: «Finally, heapify the root of tree.» и затем идет описание того, что же такое «heapify». В переводе термин «heapify» потерян, из-за этого логика становится куда более размытой.
Также третий пункт описания алгоритма «Повторяйте вышеуказанные шаги, пока размер кучи больше 1.» в оригинале написан неудачно (не очень понятно. нужно повторять шаги 1 и 2 или только 2), и тут также оставлен без изменений (причем русскоязычный вариант субъективно еще менее понятный).
В результате по описанию этого простого алгоритма, на мой взгляд, вообще мало что понятно без чтения кода или дополнительного поиска информации (что возвращает нас к теме качества статей на geeksforgeeks).
Его типичная реализация не стабильна, но может быть таковой сделана (см. Здесь).
Так себе решение. Для достижения стабильности потребуется O(n) памяти и еще больше просадит производительность. Скорее всего получится хуже по всем параметрам, чем merge sort.
Идеального алгоритмя до сих пор нет (гарантированая сложность O(n * log n), константа (или хотя бы логарифм) по памяти, стабильность).
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Пирамидальная сортировка (HeapSort)