Burstsort

FashewaƊalibinAlgorithm na tsarawaTsarin bayanaiTrieAyyuka mafi muniwasan kwaikwayonO (wn) Mafi munin yanayin sararin samaniyarikitarwa na sararin samaniyaO (wn) Mafi Kyawun?
Burstsort wasu nau'ikansa algorithms ne masu inganci wajen rarraba igiyoyi. Su nau'ikan nau'ikan radix ne amma sun fi sauri ga manyan saitin bayanai na igiyoyi na gama gari, waɗanda aka fara bugawa a shekarar 2003, tare da wasu sigar ingantawa da aka buga a shekarun baya..

Algorithms na Burstsort suna ne wanda ake  amfani da gwaji don adana prefixes na igiyoyi, tare da jerin abubuwan nuni masu girma a matsayin nodes na ƙarshe waɗanda ke ɗauke da ƙarin bayani (wanda aka fi sani da bokiti). Wasu bambance-bambancen suna kwafi wutsiyoyin kirtani cikin bokiti. Yayin da bokitin suka girma fiye da ƙayyadadden iyaka, bokitin suna "fashewa" cikin gwaje-gwaje, suna ba wa nau'in suna. Wani sabon nau'in yana amfani da ma'aunin bokiti tare da ƙananan bokiti don rage amfani da ƙwaƙwalwa. Yawancin aiwatarwa suna wakilta zuwa multikey quicksort, wani tsawo na radix quicksort mai hanyoyi uku, don tsara abubuwan da ke cikin bokitin. Ta hanyar raba shigarwar zuwa bokiti tare da prefix na gama gari, ana iya yin rarrabawa ta hanyar da ta dace da cache.

An gabatar da Burstsort a matsayin nau'in da yayi kama da nau'in MSD radix, amma ya fi sauri saboda sanin cewa ana adana cache da radix masu alaƙa kusa da juna saboda takamaiman tsarin gwaji. Yana amfani da takamaiman kirtani waɗanda galibi ake samu a zahiri. Kuma kodayake a bayyane yake iri ɗaya ne da nau'in radix, tare da sarkakiyar lokaci na O(own) (w - tsawon kalma da n - adadin kirtani da za a ware), amma saboda ingantaccen rarrabawar ƙwaƙwalwa, yakan ninka sauri akan manyan saitin kirtani. An yi masa lakabi da "mafi sauri tsarin da aka sani don tsara manyan kirtani.".

 Bayanan da aka ambata 

 Wani fashewa (C-burstsort), da sauri fiye da fashewa: Sinha, Ranjan; Zobel, Justin; Ring, David (Janairu 2006). "Sarraba Kayan Cache-Efficient ta amfani da Kwafi" (PDF). Jaridar Experimental Algorithmics . 11 (1.2): 1.2. CiteSeerX 10.1.85.3498. [Inda Aka Ɗauko Hoto da ke shafi na 10.1145/1187439. S2CID 3184411. An adana shi daga asali (PDF) a 2007-10-01. An samo shi a 2007-05-31."Sarraba Kayan Cache-Efficient ta amfani da Kwafi"  (PDF) . Jaridar Experimental Algorithmics . 11 (1.2): 1.2. CiteSeerX 10.1.85.3498.  [Inda Aka Ɗauko Hoto da ke shafi na 10.1145/1187439. S2CID 3184411.  An adana shi daga asali  (PDF)  a 2007-10-01. . An samo shi a 2007-05-31.
 Nau'in bayanan da aka yi amfani da su a cikin fashewa:  "Burst Trials: Saurin, Tsarin Bayanai mai Inganci don Maɓallan Kirtani" (PDF). ACM Transactions akan Tsarin Bayanai. 20 (2): 192–223. CiteSeerX 10.1.1.18.3499. Rubuce-rubuce na 10.1145/506309.506312. S2CID 14122377. An adana shi daga asali (PDF) a 2013-12-05. An samo shi a 2007-09-25."Burst Trials: Saurin, Tsarin Bayanai mai Inganci don Maɓallan Kirtani"  (PDF) . ACM Transactions akan Tsarin Bayanai. 20 (2): 192–. CiteSeerX 10.1.1.18.3499.  Rubuce-rubuce na 10.1145/506309.506312. S2CID 14122377.  An adana shi daga asali  (PDF)  a 2013-12-05. . An samo shi a 2007-09-25.



 A burstsort aiwatarwa a Java: burstsort4j
 Judy arrays wani nau'i ne na kwafin fashewa: C aiwatarwa
Rukuni:Shafuka masu fassarorin da ba'a duba ba