Burstsort

Burstsort y sus variantes son algoritmos eficientes en caché para ordenar cadenas . Son variantes del tradicional algoritmo de ordenación por radix , pero más rápidos para grandes conjuntos de datos de cadenas comunes. Se publicaron por primera vez en 2003, y posteriormente se publicaron algunas versiones optimizadas. ^{[ 1 ]}

Los algoritmos Burstsort utilizan un trie para almacenar prefijos de cadenas, con matrices de punteros de tamaño creciente como nodos finales que contienen sufijos únicos y ordenados (denominados cubetas ). Algunas variantes copian las colas de las cadenas en las cubetas. A medida que las cubetas superan un umbral predeterminado, se dividen en tries, lo que da nombre al algoritmo. Una variante más reciente utiliza un índice de cubetas con subcubetas más pequeñas para reducir el uso de memoria. La mayoría de las implementaciones delegan en el algoritmo Quicksort multikey, una extensión del Quicksort de radix de tres vías, para ordenar el contenido de las cubetas. Al dividir la entrada en cubetas con prefijos comunes, la ordenación se puede realizar de forma eficiente en cuanto al uso de caché.

Burstsort se introdujo como un algoritmo de ordenación similar a MSD radix sort ^{[ 1 ]} , pero más rápido gracias a que tiene en cuenta el almacenamiento en caché y las bases relacionadas se almacenan más cerca unas de otras debido a las particularidades de la estructura del trie. Aprovecha las particularidades de las cadenas que se encuentran habitualmente en el mundo real. Y aunque asintóticamente es igual que radix sort, con una complejidad temporal de O ( wn ) ( w – longitud de palabra y n – número de cadenas a ordenar), pero debido a una mejor distribución de la memoria tiende a ser el doble de rápido en grandes conjuntos de datos de cadenas. Se ha presentado como el "algoritmo más rápido conocido para ordenar grandes conjuntos de cadenas" ^{[ 2 ] .}

• Un derivado de burstsort (C-burstsort), más rápido que burstsort: Sinha, Ranjan; Zobel, Justin; Ring, David (enero de 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. Archivado del original (PDF) el 1 de octubre de 2007. Recuperado el 31 de mayo de 2007 .  
• El tipo de datos utilizado en burstsort: Heinz, Steffen; Zobel, Justin; Williams, Hugh E. (abril de 2002). "Burst Tries: una estructura de datos rápida y eficiente para claves de cadena" (PDF) . ACM Transactions on Information Systems . 20 (2): 192– 223. CiteSeerX 10.1.1.18.3499 . doi : 10.1145/506309.506312 . S2CID 14122377. Archivado del original (PDF) el 5 de diciembre de 2013. Recuperado el 25 de septiembre de 2007 .  
• Sinha, Ranjan; Zobel, Justin (2003). "Ordenación eficiente basada en árboles de prefijos de grandes conjuntos de cadenas" (PDF) . Actas de la 26.ª Conferencia Australiana de Ciencias de la Computación . Vol.  16. Sociedad Australiana de Computación. pp. 11–18 . CiteSeerX 10.1.1.12.2757 . ISBN   978-0-909-92594-9Archivado del original (PDF) el 8 de febrero de 2012. Consultado el 25 de septiembre de 2007 .
• Sinha, Ranjan; Wirth, Anthony (marzo de 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 . 

• Implementación de burstsort en Java: burstsort4j
• Los arreglos Judy son un tipo de ordenamiento por explosión de copia: implementación en C