La clasificación por cubos , o clasificación por contenedores , es un algoritmo de clasificación que funciona distribuyendo los elementos de una matriz en varios contenedores . Luego, cada depósito se clasifica individualmente, ya sea mediante un algoritmo de clasificación diferente o aplicando de forma recursiva el algoritmo de clasificación de depósitos. Es un tipo de distribución , una generalización del tipo de casillero , y es un primo del tipo de base en el tipo de dígito más a menos significativo. La clasificación de depósitos se puede implementar con comparaciones y, por lo tanto, también se puede considerar un algoritmo de clasificación de comparación . La complejidad computacional depende del algoritmo utilizado para ordenar cada depósito, la cantidad de depósitos que se utilizarán y si la entrada se distribuye uniformemente.
Clase | Algoritmo de clasificación |
---|---|
Estructura de datos | Formación |
Rendimiento en el peor de los casos | |
Rendimiento medio | , donde k es el número de depósitos. . |
Complejidad espacial en el peor de los casos |
La clasificación de cubos funciona de la siguiente manera:
- Configure una matriz de "cubos" inicialmente vacíos.
- Dispersión : repase la matriz original, colocando cada objeto en su cubo.
- Clasifique cada balde que no esté vacío.
- Recopilar : visite los depósitos en orden y vuelva a colocar todos los elementos en la matriz original.
Pseudocódigo
la función bucketSort (array, k) es cubos ← nueva matriz de k listas vacías M ← el valor máximo de clave en la matriz para i = 1 a longitud (array) hacer inserto array [i] en cubos [piso (k × array [i] / M)] para i = 1 a k hacer nextSort (depósitos [i]) devuelve la concatenación de cubos [1], ...., cubos [k]
Aquí matriz es la matriz que se va a ordenar y k es el número de cubos que se utilizarán. El valor máximo de clave se puede calcular en tiempo lineal buscando todas las claves una vez. La función de piso debe usarse para convertir un número flotante en un entero. La función nextSort es una función de clasificación que se utiliza para clasificar cada depósito. Convencionalmente, se usaría la ordenación por inserción , pero también se podrían usar otros algoritmos. El uso de bucketSort en sí mismo como nextSort produce un relativo de ordenación de base ; en particular, el caso n = 2 corresponde a quicksort (aunque potencialmente con malas opciones de pivote).
Análisis
Análisis del peor de los casos
La clasificación por cubos es principalmente útil cuando la entrada se distribuye uniformemente en un rango. Cuando la entrada contiene varias claves cercanas entre sí (agrupamiento), es probable que esos elementos se coloquen en el mismo depósito, lo que da como resultado que algunos depósitos contengan más elementos que el promedio. El peor de los casos ocurre cuando todos los elementos se colocan en un solo cubo. El rendimiento general estaría entonces dominado por el algoritmo utilizado para clasificar cada segmento, que normalmente es clasificación de inserción , lo que hace que la clasificación de cubos sea menos óptima que algoritmos de clasificación por comparación , como la clasificación por combinación .
Análisis de casos promedio
Considere el caso de que la entrada se distribuya uniformemente. El primer paso, que es inicializar los depósitos y encontrar el valor máximo de clave en la matriz, se puede realizar enhora. Si la división y la multiplicación se pueden hacer en tiempo constante, entonces esparcir cada elemento en su balde también cuesta. Suponga que la clasificación por inserción se usa para clasificar cada segmento, luego el tercer paso cuesta, dónde es la longitud del cubo indexada . Ya que nos referimos al tiempo promedio, la expectativatiene que ser evaluado en su lugar. Dejar ser la variable aleatoria que es si elemento se coloca en un cubo , y de lo contrario. Tenemos. Por lo tanto,
La última línea separa la suma en el caso. y el caso . Dado que la posibilidad de que un objeto se distribuya a un cubo es , es 1 con probabilidad y 0 en caso contrario.
Con la suma, sería
Finalmente, la complejidad sería .
El último paso de la clasificación de depósitos, que consiste en concatenar todos los objetos ordenados en cada depósito, requierehora. Por tanto, la complejidad total es. Tenga en cuenta que si k se elige, luego se ejecuta la clasificación de cubos tiempo promedio, dada una entrada uniformemente distribuida. [1]
Optimizaciones
Una optimización común es volver a colocar los elementos sin clasificar de los depósitos en la matriz original primero , luego ejecutar la ordenación por inserción sobre la matriz completa; debido a que el tiempo de ejecución de la ordenación por inserción se basa en qué tan lejos está cada elemento de su posición final, el número de comparaciones sigue siendo relativamente pequeño y la jerarquía de la memoria se explota mejor almacenando la lista de forma contigua en la memoria. [2]
Variantes
Tipo de cubo genérico
La variante más común de clasificación de cubos opera en una lista de n entradas numéricas entre cero y algún valor máximo M y divide el rango de valores en n cubos, cada uno de tamaño M / n . Si cada depósito se ordena mediante la ordenación por inserción , se puede mostrar que la ordenación se ejecuta en el tiempo lineal esperado (donde se toma el promedio de todas las entradas posibles). [3] Sin embargo, el rendimiento de este tipo se degrada con la agrupación; si hay muchos valores juntos, todos caerán en un solo cubo y se clasificarán lentamente. Esta degradación del rendimiento se evita en el algoritmo de clasificación de cubos original suponiendo que la entrada se genera mediante un proceso aleatorio que distribuye los elementos de manera uniforme en el intervalo [0,1) . [1]
ProxmapSort
Similar al ordenamiento genérico de cubos como se describe arriba, ProxmapSort funciona dividiendo un arreglo de claves en subarreglos mediante el uso de una función de "clave de mapa" que preserva un orden parcial en las claves; a medida que se agrega cada clave a su subarreglo, la ordenación por inserción se usa para mantener ese subarreglo ordenado, lo que da como resultado que todo el arreglo esté ordenado cuando ProxmapSort se completa. ProxmapSort se diferencia de los tipos de depósito en su uso de la clave del mapa para colocar los datos aproximadamente donde pertenecen en orden ordenado, produciendo un "mapa prox" - un mapeo de proximidad - de las claves.
Orden de histograma
Otra variante de la clasificación de cubos conocida como clasificación por histograma o clasificación por recuento agrega una pasada inicial que cuenta la cantidad de elementos que caerán en cada cubeta mediante una matriz de conteo. [4] Con esta información, los valores de la matriz se pueden organizar en una secuencia de cubos en el lugar mediante una secuencia de intercambios, sin dejar espacio para el almacenamiento de cubos. [ verificación fallida ]
Tipo de cartero
El tipo de cartero es una variante del tipo de cubo que aprovecha una estructura jerárquica de elementos, normalmente descritos por un conjunto de atributos. Este es el algoritmo utilizado por las máquinas clasificadoras de cartas en las oficinas de correos: el correo se clasifica primero entre nacional e internacional; luego por estado, provincia o territorio; luego por la oficina de correos de destino; luego por rutas, etc. Dado que las claves no se comparan entre sí, el tiempo de clasificación es O ( cn ), donde c depende del tamaño de la clave y del número de cubos. Esto es similar a una ordenación de base que funciona "de arriba hacia abajo" o "primero el dígito más significativo". [5]
Orden aleatorio
La ordenación aleatoria [6] es una variante de la ordenación de cubos que comienza eliminando el primer 1/8 de los n elementos que se van a ordenar, los ordena de forma recursiva y los coloca en una matriz. Esto crea n / 8 "cubos" a los que se distribuyen los 7/8 restantes de los elementos. A continuación, se clasifica cada "depósito" y los "depósitos" se concatenan en una matriz ordenada.
Comparación con otros algoritmos de clasificación
La clasificación por cubos puede verse como una generalización de la clasificación por conteo ; de hecho, si cada cubeta tiene un tamaño 1, la clasificación por cubeta degenera en clasificación por conteo. El tamaño de depósito variable de la clasificación de depósito le permite utilizar la memoria O ( n ) en lugar de la memoria O ( M ), donde M es el número de valores distintos; a cambio, renuncia a contar el comportamiento del peor de los casos O ( n + M ) de sort .
La ordenación de cubos con dos cubos es efectivamente una versión de ordenación rápida en la que el valor de pivote siempre se selecciona para ser el valor medio del rango de valores. Si bien esta elección es eficaz para entradas distribuidas uniformemente, otros medios de elegir el pivote en el ordenamiento rápido, como los pivotes seleccionados al azar, lo hacen más resistente al agrupamiento en la distribución de entrada.
El algoritmo mergesort de n vías también comienza distribuyendo la lista en n sublistas y ordenando cada una; sin embargo, las sublistas creadas por mergesort tienen rangos de valores superpuestos y, por lo tanto, no pueden recombinarse mediante una simple concatenación como en la ordenación de cubos. En su lugar, deben estar intercalados mediante un algoritmo de combinación. Sin embargo, este gasto adicional se compensa con la fase de dispersión más simple y la capacidad de garantizar que cada sublista tenga el mismo tamaño, lo que proporciona un buen límite de tiempo en el peor de los casos.
La ordenación por base de arriba hacia abajo se puede ver como un caso especial de ordenación de cubos donde tanto el rango de valores como el número de cubos están restringidos a ser una potencia de dos. En consecuencia, el tamaño de cada cubo también es una potencia de dos y el procedimiento se puede aplicar de forma recursiva. Este enfoque puede acelerar la fase de dispersión, ya que solo necesitamos examinar un prefijo de la representación de bits de cada elemento para determinar su cubo.
Referencias
- ^ a b Thomas H. Cormen ; Charles E. Leiserson ; Ronald L. Rivest y Clifford Stein . Introducción a los algoritmos .
La clasificación de cubos se ejecuta en tiempo lineal en promedio. Al igual que la ordenación de conteo, la ordenación de cubos es rápida porque asume algo sobre la entrada. Mientras que la ordenación por recuento asume que la entrada consta de números enteros en un rango pequeño, la ordenación por cubos supone que la entrada se genera mediante un proceso aleatorio que distribuye los elementos de manera uniforme en el intervalo [0,1) . La idea de la clasificación de cubos es dividir el intervalo [0, 1) en n subintervalos de igual tamaño, o cubos, y luego distribuir los n números de entrada en los cubos. Dado que las entradas se distribuyen uniformemente en [0, 1) , no esperamos que caigan muchos números en cada segmento. Para producir el resultado, simplemente clasificamos los números en cada segmento y luego revisamos los segmentos en orden, enumerando los elementos en cada uno.
- ^ Corwin, E. y Logar, A. "Clasificación en tiempo lineal - variaciones en el tipo de cubo". Journal of Computing Sciences in Colleges , 20, 1, págs. 197–202. Octubre de 2004.
- ^ Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein . Introducción a los algoritmos , segunda edición. MIT Press y McGraw-Hill, 2001. ISBN 0-262-03293-7 . Sección 8.4: Clasificación de cubos, págs. 174–177.
- ^ Diccionario de algoritmos y estructuras de datos del NIST: clasificación de histograma
- ^ http://www.rrsd.com/psort/cuj/cuj.htm
- ^ Un nuevo tipo revolucionario de John Cohen 26 de noviembre de 1997
- Paul E. Black "Tipo de cartero" del Diccionario de algoritmos y estructuras de datos en NIST .
- Robert Ramey , el diario de usuarios C "El tipo del cartero", agosto de 1992
- Diccionario de NIST de algoritmos y estructuras de datos: clasificación de cubos
enlaces externos
- Código de clasificación del cucharón para Ansi C
- Variante de clasificación de cubos con demostración