Pull to refresh
  • by relevance
  • by date
  • by rating

J-сортировка

Programming *Java *Algorithms *

Пирамидальная сортировка (она же сортировка кучей) – классический алгоритм который, пожалуй, должен знать любой программист. Старая добрая «пирамидка» примечательна тем, что в независимости от набора данных у неё одна и та же сложность по времени (причём, очень пристойная) – O(n log n). Лучших и вырожденных случаев для неё нет.

С момента изобретения метода (а в этом году алгоритм празднует свой полувековой юбилей) было немало охочих кардинально оптимизировать процесс накладывания сортирующих куч. Тернарная пирамидальная сортировка, плавная сортировка, сортировка декартовым деревом – вот неполный список инноваций. Перечисленные алгоритмы хотя при тестировании и опережают оригинал по абсолютной скорости кто на 12, а кто и на 25%, в оценке временной сложности всё равно крутятся вокруг O(n log n). При этом данные методы весьма изощрённо реализованы.

Своё видение пирамидальной сортировки предложил и скромный труженик Университета Манитобы Джейсон Моррисон. При этом способ в некоторых случаях по скорости приближается к O(n).

Так ещё метод и прост до безобразия
Total votes 57: ↑53 and ↓4 +49
Views 83K
Comments 17

И ещё о сортировках

Programming *C++ *Algorithms *Processing *

И ещё о сортировках


Рискну опять поднять эту тему. Начну со ссылки на статью Михаила Опанасенко (oms7), очень впечатляющую по объёмам проделанной работы, а также по количеству приведёных ссылок. Свой материал начал готовить, не зная об этой публикации, что впоследствии, после ознакомления привело к необходимости его существенной переработки. Для тех, кто уже прочитал эту статью, сообщаю, что в моём материале, исследуются более разнообразные по типам данные, в частности, строки и вещественные числа, используются библиотеки boost и bsd, а также затрагиваются некоторые другие отсутствующие в названной статье темы.
Читать дальше →
Total votes 25: ↑23 and ↓2 +21
Views 17K
Comments 53

Сортировка n-нарной пирамидой

Edison corporate blog Python *Programming *Perfect code *Algorithms *

Сортировку кучей (она же — пирамидальная сортировка) на Хабре уже поминали добрым словом не раз и не два, но это всегда была достаточно общеизвестная информация. Обычную бинарную кучу знают все, но ведь в теории алгоритмов также есть:

n-нарная куча; куча куч, основанная на числах Леонардо; дерамида (гибрид кучи и двоичного дерева поиска); турнирная мини-куча; зеркальная (обратная) куча; слабая куча; юнгова куча; биномиальная куча; и бог весть ещё какие кучи…

И умнейшие представители computer science в разные годы предложили свои алгоритмы сортировки с помощью этих пирамидальных структур. Кому интересно, что у них получилось — для тех начинаем небольшую серию статей, посвящённую вопросам сортировки с помощью этих структур. Мир куч многообразен — надеюсь, вам будет интересно.
Траффик
Total votes 25: ↑24 and ↓1 +23
Views 7.1K
Comments 5

Восходящая сортировка кучей

Edison corporate blog High performance *Python *Programming *Algorithms *

Это заключительная статья из серии про сортировки кучей. В предыдущих лекциях мы рассмотрели весьма разнообразные кучные структуры, показывающих отличные результаты по скорости. Напрашивается вопрос: а какая куча наиболее эффективна, если речь идёт о сортировке? Ответ таков: та, которую мы рассмотрим сегодня.
Траффик
Total votes 12: ↑12 and ↓0 +12
Views 4.2K
Comments 6