Cubesort
Cubesort je paralelni algoritam za sortiranje koji pravi samo-balansirajući multi-dimenzioni niz od vrednosti koje treba da se sortiraju. Pošto su ose sličnih dužina, ova struktura odokativno liči na kocku. Pošto je svaka vrednost ubačena, kocka je u stanju da vrlo brzo sve prevede u niz.[1]
| Klasa | Algoritam za sortiranje |
|---|---|
| Struktura podataka | Niz |
| Najgora performanca | O(n log n) |
| Najgora prostorna kompleksnost | Θ(n) |
Implementacija za ovaj algoritam je objavljena za programski jezik C u 2014. godini.[2]
Operacija uredi
Ovaj algoritam koristi specijalizovanu binarnu pretragu na svakoj osi da bi našao lokaciju gde da ubaci zadati element. Kada osa previše poraste deli se na pola. Lokalnost referenciranja je optimalna jer se samo 4 binarne pretrage koriste na malom nizu za ubacivanje jednog elementa. Koristeći mnogo malih dinamičnih nizova velika cena ubacivanja jednog velikog niza je izbegnuta.
Reference uredi
- ^ Cypher, Robert; Sanz, Jorge L.C (1992). „Cubesort: A parallel algorithm for sorting N data items with S-sorters”.
- ^ „Cubesort”.
Literatura uredi
- Cubesort description and implementation in C Arhivirano na sajtu Wayback Machine (23. decembar 2015)
- Tetsuo Asano (ur.). „Algorithms and Computation: 7th International Symposium, ISAAC '96, Osaka”. str. 187—188.