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