Комментарии 6
Изящный алгоритм с хорошими гарантиями производительности, когда изучил впервые, был очень впечатлён.
+3
Полезная статья! Очень полезная! Очень очень полезная! Но как по мне слишком большой порог вхождения, можно сначала пузырьковую сортировку на всех языках мира?
0
Спасибо, нам нужно больше копипасты с гитхаба.
+1
Я понимаю, что это всего лишь перевод статьи с 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).
0
Его типичная реализация не стабильна, но может быть таковой сделана (см. Здесь).
Так себе решение. Для достижения стабильности потребуется O(n) памяти и еще больше просадит производительность. Скорее всего получится хуже по всем параметрам, чем merge sort.
Идеального алгоритмя до сих пор нет (гарантированая сложность O(n * log n), константа (или хотя бы логарифм) по памяти, стабильность).
+1
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Пирамидальная сортировка (HeapSort)