Burstsort

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..^[1]

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.".^[2]

• 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.Sinha, Ranjan; Zobel, Justin; Ring, David (January 2006). "Cache-Efficient String Sorting Using Copying" (PDF). Journal of Experimental Algorithmics. 11 (1.2): 1.2. CiteSeerX 10.1.1.85.3498. doi:10.1145/1187436.1187439. S2CID 3184411. Archived from the original (PDF) on 2007-10-01. Retrieved 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 Archived 2007-10-01 at the Wayback Machine (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.Heinz, Steffen; Zobel, Justin; Williams, Hugh E. (April 2002). "Burst Tries: A Fast, Efficient Data Structure for String Keys" (PDF). ACM Transactions on Information Systems. 20 (2): 192–223. CiteSeerX 10.1.1.18.3499. doi:10.1145/506309.506312. S2CID 14122377. Archived from the original (PDF) on 2013-12-05. Retrieved 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 Archived 2013-12-05 at the Wayback Machine (PDF) a 2013-12-05. . An samo shi a 2007-09-25.
•  
• Sinha, Ranjan; Wirth, Anthony (March 2010). "Engineering Burstsort: Towards Fast In-Place String Sorting" (PDF). ACM Journal of Experimental Algorithmics. 15 (2.5): 1–24. doi:10.1145/1671970.1671978. S2CID 16410080.

• A burstsort aiwatarwa a Java: burstsort4j
• Judy arrays wani nau'i ne na kwafin fashewa: C aiwatarwa

1. ↑ Sinha, R.; Zobel, J. (2005). "Cache-conscious sorting of large sets of strings with dynamic tries" (PDF). Journal of Experimental Algorithmics. 9: 1.5. CiteSeerX 10.1.1.599.861. doi:10.1145/1005813.1041517. S2CID 10807318.
2. ↑ "Burstsort: Fastest known algorithm to sort large set of strings | Hacker News".