Cubesort - Cubesort - Wikipedia
 | Téma tohoto článku nemusí splňovat požadavky Wikipedie obecný pokyn k notabilitě. (Září 2014) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) |
 | tento článek příliš spoléhá na Reference na primární zdroje. (Září 2014) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) |
| Třída | Algoritmus řazení |
|---|---|
| Datová struktura | Pole |
| Nejhorší případ výkon | Ó(n log n) |
| Nejhorší případ složitost prostoru | Θ (n) |
Cubesort je paralela třídicí algoritmus který vytváří samovyvažující vícerozměrné pole z klíčů, které se mají třídit. Protože osy mají podobnou délku, struktura se podobá krychli. Po vložení každého klíče lze kostku rychle převést na pole.[1]
Implementace cubesortu napsaná v jazyce C byla zveřejněna v roce 2014.[2]
Úkon
Cubesortův algoritmus používá specializovaný binární vyhledávání na každé ose vyhledejte umístění pro vložení prvku. Když osa roste příliš velká, je rozdělena. Lokalita reference je optimální, protože pro každé vložení jsou prováděna pouze čtyři binární vyhledávání na malých polích. Použitím mnoha malých dynamických polí se zabrání vysokým nákladům na vložení do jednotlivých velkých polí.
Reference
- ^ Cypher, Robert; Sanz, Jorge LC (1992). "Cubesort: Paralelní algoritmus pro třídění N datových položek pomocí S-třídičů". doi:10.1016/0196-6774(92)90016-6. Chybějící nebo prázdný
| url =(Pomoc) - ^ "Cubesort".
externí odkazy
- Popis a implementace Cubesortu v jazyce C.
- Algorithms and Computation: 7th International Symposium, ISAAC '96, Osaka ... edited Tetsuo Asano et al, pp 187-188, https://books.google.com/books?id=vilOl8JCpFUC&pg=PA188&lpg=PA188&hl=cs&f=false (mimochodem zmínka)
 | Tento algoritmy nebo datové struktury související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to. |