Burstsort

Из Википедије, слободне енциклопедије

Burstsort i njegove verzije koje služe za efikasno sortiranje niski u keš memoriji. Burstsort je brži od quicksort-a kada su u pitanju velike grupe podataka.

Burstsort algoritam koristi drvo za skladištenje prefiksnih niski, sa dinamicnim poretkom pokazivača kao krajnjih čvorova koji sadrže sortirane, jedinstvene sufikse(poznatiji kako segmenti). Neke verzije kopiraju krajeve niski u segmente. Burstsort je dobio ime tako što segmenti rastu preko predodređenog praga i onda u jednom trenutku „pucaju“. Novija verzija koristi segment registre sa manjim sub-segmentima da bi smanjili upotrebu memorije. Multikey quicksort, ekstenzija osnovnog trosmernog quicksorta je zadužen za raspoređivanje sadržaja segmeta u najvećem broju implementacija. Deljenjem unosa segmenta sa zajedničkim prefiksima, raspoređivanje može biti efektivno uređeno u keš memoriji.

Literatura[уреди]