Cubesort
| Класа | Алгоритам за сортирање |
|---|---|
| Структура података | Низ |
| Најгора перформанца | O(n log n) |
| Најгора просторна комплексност | Θ(n) |
Cubesort је паралелни алгоритам за сортирање који прави само-балансирајући мулти-димензиони низ од вредности које треба да се сортирају. Пошто су осе сличних дужина, ова структура одокативно личи на коцку. Пошто је свака вредност убачена, коцка је у стању да врло брзо све преведе у низ.[1]
Имплементација за овај алгоритам је објављена за програмски језик Ц у 2014. години.[2]
Операција
[уреди | уреди извор]Овај алгоритам користи специјализовану бинарну претрагу на свакој оси да би нашао локацију где да убаци задати елемент. Када оса превише порасте дели се на пола. Локалност референцирања је оптимална јер се само 4 бинарне претраге користе на малом низу за убацивање једног елемента. Користећи много малих динамичних низова велика цена убацивања једног великог низа је избегнута.
Референце
[уреди | уреди извор]- ^ Cypher, Robert; Sanz, Jorge L.C (1992). „Cubesort: A parallel algorithm for sorting N data items with S-sorters”.
- ^ „Cubesort”.
Литература
[уреди | уреди извор]- Cubesort description and implementation in C Архивирано на сајту Wayback Machine (23. децембар 2015)
- Tetsuo Asano (ур.). „Algorithms and Computation: 7th International Symposium, ISAAC '96, Osaka”. стр. 187—188.