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

Описание алгоритмов сортировки и сравнение их производительности

C++ *Algorithms *
Sandbox

Вступление


На эту тему написано уже немало статей. Однако я еще не видел статьи, в которой сравниваются все основные сортировки на большом числе тестов разного типа и размера. Кроме того, далеко не везде выложены реализации и описание набора тестов. Это приводит к тому, что могут возникнуть сомнения в правильности исследования. Однако цель моей работы состоит не только в том, чтобы определить, какие сортировки работают быстрее всего (в целом это и так известно). В первую очередь мне было интересно исследовать алгоритмы, оптимизировать их, чтобы они работали как можно быстрее. Работая над этим, мне удалось придумать эффективную формулу для сортировки Шелла.

Во многом статья посвящена тому, как написать все алгоритмы и протестировать их. Если говорить о самом программировании, то иногда могут возникнуть совершенно неожиданные трудности (во многом благодаря оптимизатору C++). Однако не менее трудно решить, какие именно тесты и в каких количествах нужно сделать. Коды всех алгоритмов, которые выложены в данной статье, написаны мной. Доступны и результаты запусков на всех тестах. Единственное, что я не могу показать — это сами тесты, поскольку они весят почти 140 ГБ. При малейшем подозрении я проверял и код, соответствующий тесту, и сам тест. Надеюсь, что статья Вам понравится.
Читать дальше →
Total votes 80: ↑76 and ↓4 +72
Views 392K
Comments 55

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

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

Пирамидальная сортировка, сортировка слиянием и выпуклая оболочка

OTUS corporate blog Programming *Algorithms *Big Data *
Translation

Куча (heap) — это не что иное, как двоичное дерево с некоторыми дополнительными правилами, которым оно должно следовать: во-первых, оно всегда должно иметь структуру кучи, где все уровни двоичного дерева заполняются слева направо, и, во-вторых, оно должно быть упорядочено в виде max-кучи или min-кучи. В качестве примера я буду использовать min-кучу.

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

Читать далее
Total votes 14: ↑10 and ↓4 +6
Views 4K
Comments 6

Пирамидальная сортировка выбором

OTUS corporate blog Algorithms *

Один из самых необычных алгоритмов сортировки массива  - это HeapSort, в основе которого лежит алгоритм сортировки выбором, используется структура данных «куча» для быстрого нахождения максимального элемента, а также способ хранения двоичного дерева в линейном массиве. Разберёмся со всем по порядку.

Поехали!
Total votes 13: ↑10 and ↓3 +7
Views 3.7K
Comments 4