Кубосорт
 | В этой статье есть несколько проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти шаблонные сообщения )
|
| Сорт | Алгоритм сортировки |
|---|---|
| Структура данных | Множество |
| Худшая производительность | О ( нлогн n) |
| Наихудшая пространственная сложность | Θ( п ) |
| Оптимальный | ? |
Cubesort — это алгоритм параллельной сортировки , который создает самобалансирующийся многомерный массив из ключей, подлежащих сортировке. Поскольку оси одинаковой длины, конструкция напоминает куб. После вставки каждого ключа куб можно быстро преобразовать в массив. [1]
Реализация кубической сортировки, написанная на C, была опубликована в 2014 году. [2]
Операция
[ редактировать ]Алгоритм Cubesort использует специализированный двоичный поиск по каждой оси, чтобы найти место для вставки элемента. Когда ось становится слишком большой, она расщепляется. Локальность ссылки является оптимальной, поскольку для каждой вставки выполняется только четыре двоичных поиска в небольших массивах. Используя множество небольших динамических массивов, можно избежать высоких затрат на вставку в один большой массив.
Ссылки
[ редактировать ]- ^ Сайфер, Роберт; Санс, Хорхе LC (1992). «Cubesort: параллельный алгоритм сортировки N элементов данных с помощью S-сортировщиков». Журнал алгоритмов . 13 (2): 211–234. дои : 10.1016/0196-6774(92)90016-6 .
- ^ Игорь ван ден Ховен (22 июня 2014 г.). «Кубсорт» . codeproject.com .
Внешние ссылки
[ редактировать ]- «Описание и реализация Cubesort на C» . Архивировано из оригинала 08.10.2020.
- Нидермайер, Рольф (1996). «Рекурсивно делимые проблемы». Алгоритмы и вычисления . Конспекты лекций по информатике. Том. 1178. Шпрингер Берлин Гейдельберг. стр. 187–188. дои : 10.1007/BFb0009494 . eISSN 1611-3349 . ISBN 978-3-540-62048-8 . ISSN 0302-9743 . (мимо упоминания)
 | Эта алгоритмам или структурам данных, статья, посвященная является незавершенной . Вы можете помочь Википедии, расширив ее . |