Cubesort - Cubesort
Класс | Алгоритм сортировки |
---|---|
Структура данных | Массив |
Пессимистический производительность | O ( п войти п ) |
Сложность пространства в наихудшем случае | Θ ( п ) |
Cubesort - это алгоритм параллельной сортировки, который строит самобалансирующийся многомерный массив из ключей, которые нужно отсортировать. Поскольку оси имеют одинаковую длину, конструкция напоминает куб. После вставки каждого ключа куб можно быстро преобразовать в массив.
Реализация cubesort, написанная на C, была опубликована в 2014 году.
Операция
Алгоритм Cubesort использует специальный двоичный поиск по каждой оси, чтобы найти место для вставки элемента. Когда ось становится слишком большой, она разделяется. Местоположение ссылки является оптимальным, так как для каждой вставки выполняется только четыре бинарных поиска в небольших массивах. Использование множества небольших динамических массивов позволяет избежать высоких затрат на вставку в отдельные большие массивы.
Ссылки
внешние ссылки
- Описание и реализация Cubesort на C
- Алгоритмы и вычисления: 7-й Международный симпозиум, ISAAC '96, Осака ... под редакцией Тецуо Асано и др., Стр. 187-188, https://books.google.com/books?id=vilOl8JCpFUC&pg=PA188&lpg=PA188&hl=en&f= ложь (мимолетное упоминание)
Эта статья, посвященная алгоритмам или структурам данных, является незавершенной . Вы можете помочь Википедии, расширив ее . |