Burstsort - Burstsort

Burstsort
Clase Algoritmo de clasificación
Estructura de datos Trie
Rendimiento en el peor de los casos O ( wn )
Complejidad espacial en el peor de los casos O ( wn )

Burstsort y sus variantes son algoritmos eficientes en caché para ordenar cadenas . Son variantes del tipo de radix tradicional, pero más rápidas para grandes conjuntos de datos de cadenas comunes, publicadas por primera vez en 2003, con algunas versiones optimizadoras publicadas en años posteriores.

Los algoritmos Burstsort utilizan un trie para almacenar prefijos de cadenas, con matrices de punteros que se pueden aumentar como nodos finales que contienen sufijos únicos y ordenados (denominados depósitos ). Algunas variantes copian las colas de las cuerdas en los cubos. A medida que los cubos crecen más allá de un umbral predeterminado, los cubos se "reventan" en intentos, dando al género su nombre. Una variante más reciente usa un índice de depósito con subgrupos más pequeños para reducir el uso de memoria. La mayoría de las implementaciones delegan en el ordenamiento rápido de múltiples claves, una extensión del ordenamiento rápido de radix de tres vías, para ordenar el contenido de los depósitos. Al dividir la entrada en depósitos con prefijos comunes, la clasificación se puede realizar de manera eficiente en caché.

Burstsort se introdujo como un tipo que es similar al tipo de radix de MSD , pero es más rápido debido a que es consciente de que el almacenamiento en caché y los radixes relacionados se almacenan más cerca entre sí debido a las características específicas de la estructura de trie. Aprovecha las características específicas de las cadenas que normalmente se encuentran en el mundo real. Y aunque asintóticamente es lo mismo que el ordenamiento por radix, con una complejidad de tiempo de O ( wn ) ( w - longitud de palabra yn - 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. Ha sido catalogado como el "algoritmo conocido más rápido para clasificar grandes conjuntos de cadenas".

Referencias

enlaces externos