Cubesort - Cubesort
Clase | Algoritmo de clasificación |
---|---|
Estructura de datos | Formación |
Rendimiento en el peor de los casos | O ( n log n ) |
Complejidad espacial en el peor de los casos | Θ ( n ) |
Cubesort es un algoritmo de clasificación en paralelo que crea una matriz multidimensional de equilibrio automático a partir de las claves que se van a clasificar. Como los ejes tienen una longitud similar, la estructura se asemeja a un cubo. Después de insertar cada clave, el cubo se puede convertir rápidamente en una matriz.
En 2014 se publicó una implementación de cubesort escrita en C.
Operación
El algoritmo de Cubesort utiliza una búsqueda binaria especializada en cada eje para encontrar la ubicación para insertar un elemento. Cuando un eje crece demasiado, se divide. La localidad de referencia es óptima ya que solo se realizan cuatro búsquedas binarias en arreglos pequeños para cada inserción. Al usar muchos arreglos dinámicos pequeños, se evita el alto costo de inserción en arreglos grandes individuales.
Referencias
enlaces externos
- Descripción e implementación de Cubesort en C
- Algoritmos y Computación: 7mo Simposio Internacional, ISAAC '96, Osaka ... editado por Tetsuo Asano et al, pp 187-188, https://books.google.com/books?id=vilOl8JCpFUC&pg=PA188&lpg=PA188&hl=en&f= falso (mención pasajera)
Este artículo relacionado con algoritmos o estructuras de datos es un fragmento . Puedes ayudar a Wikipedia expandiéndolo . |