Clasificación de cubos

Algoritmo de clasificación

Los elementos se distribuyen entre contenedores.

Luego, los elementos se clasifican dentro de cada contenedor.

La clasificación de depósitos , o clasificación de contenedores , es un algoritmo de clasificación que funciona distribuyendo los elementos de una matriz en varios depósitos. Luego, cada depósito se clasifica individualmente, ya sea utilizando un algoritmo de clasificación diferente o aplicando recursivamente el algoritmo de clasificación de depósitos. Es una clasificación de distribución , una generalización de la clasificación por casillero que permite múltiples claves por depósito, y es un primo de la clasificación por base en el tipo de dígitos de mayor a menor significado. La clasificación por depósitos se puede implementar con comparaciones y, por lo tanto, también se puede considerar un algoritmo de clasificación por comparación . La complejidad computacional depende del algoritmo utilizado para ordenar cada depósito, la cantidad de depósitos a utilizar y si la entrada está distribuida uniformemente.

La clasificación de depósitos funciona de la siguiente manera:

1. Configure una serie de "cubos" inicialmente vacíos.
2. Dispersión : revisa la matriz original y coloca cada objeto en su depósito.
3. Clasifique cada cubo que no esté vacío.
4. Reunir : visite los depósitos en orden y vuelva a colocar todos los elementos en la matriz original.

Pseudocódigo

función cubetaOrdenar (matriz, k) es cubos ← nueva matriz de k listas vacías M ← 1 + el valor clave máximo en la matriz para i = 0 a longitud (matriz) , inserte la matriz [i] en cubos [piso (k × matriz [i] / M)]  para i = 0 a k  siguienteOrdenar(cubos[i]) devolver la concatenación de depósitos [0], ...., depósitos [k]

Sea matriz la matriz que se va a ordenar y k la cantidad de depósitos que se van a utilizar. Se puede calcular el valor de clave máximo en tiempo lineal iterando sobre todas las claves una vez. La función Floor debe usarse para convertir un número flotante en un número entero (y posiblemente también para convertir tipos de datos). La función nextSort es una función de clasificación que se utiliza para ordenar cada depósito. Convencionalmente, se utiliza la ordenación por inserción , pero también se podrían usar otros algoritmos, como la ordenación por selección o la ordenación por combinación . El uso del propio bucketSort como nextSort produce un relativo de tipo base ; en particular, el caso n = 2 corresponde a la ordenación rápida (aunque potencialmente con malas elecciones de pivote).

Análisis

Análisis del peor de los casos

Cuando la entrada contiene varias claves cercanas entre sí (agrupación), 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 depósito. El rendimiento general estaría entonces dominado por el algoritmo utilizado para ordenar cada depósito, por ejemplo, algoritmos de clasificación por inserción o de comparación , como el de clasificación por combinación . ${\displaystyle O(n^{2})}$ ${\displaystyle O(n\log(n))}$

Análisis de casos promedio

Considere el caso en que la entrada está distribuida uniformemente. El primer paso, que es inicializar los depósitos y encontrar el valor clave máximo en la matriz, se puede realizar a tiempo. Si la división y la multiplicación se pueden realizar en tiempo constante, entonces también cuesta dispersar cada elemento en su cubo . Supongamos que se utiliza la clasificación por inserción para ordenar cada depósito, luego el tercer paso cuesta , donde se indexa la longitud del depósito . Dado que nos referimos al tiempo promedio, en su lugar se debe evaluar la expectativa. Sea la variable aleatoria que es si el elemento se coloca en el cubo y en caso contrario. Tenemos . Por lo tanto, ${\displaystyle O(n)}$ ${\displaystyle O(n)}$ ${\displaystyle O(\textstyle \sum _{i=1}^{k}\displaystyle n_{i}^{2})}$ ${\displaystyle n_{i}}$ ${\displaystyle i}$ ${\displaystyle E(n_{i}^{2})}$ ${\displaystyle X_{ij}}$ ${\displaystyle 1}$ ${\displaystyle j}$ ${\displaystyle i}$ ${\displaystyle 0}$ ${\displaystyle n_{i}=\sum _{j=1}^{n}X_{ij}}$

${\displaystyle {\begin{aligned}E(n_{i}^{2})&=E\left(\sum _{j=1}^{n}X_{ij}\sum _{l=1}^{n}X_{il}\right)\\&=E\left(\sum _{j=1}^{n}\sum _{l=1}^{n}X_{ij}X_{il}\right)\\&=E\left(\sum _{j=1}^{n}X_{ij}^{2}\right)+E\left(\sum _{1\leq j,l\leq n}\sum _{j\neq l}X_{ij}X_{il}\right)\end{aligned}}}$

La última línea separa el resumen en caso y caso . Dado que la probabilidad de que un objeto se distribuya en el depósito es 1 con probabilidad y 0 en caso contrario. ${\displaystyle j=l}$ ${\displaystyle j\neq l}$ ${\displaystyle i}$ ${\displaystyle 1/k}$ ${\displaystyle X_{ij}}$ ${\displaystyle 1/k}$

${\displaystyle E(X_{ij}^{2})=1^{2}\cdot \left({\frac {1}{k}}\right)+0^{2}\cdot \left(1-{\frac {1}{k}}\right)={\frac {1}{k}}}$

${\displaystyle E(X_{ij}X_{ik})=1\cdot \left({\frac {1}{k}}\right)\left({\frac {1}{k}}\right)={\frac {1}{k^{2}}}}$

Con la sumatoria seria

${\displaystyle E\left(\sum _{j=1}^{n}X_{ij}^{2}\right)+E\left(\sum _{1\leq j,k\leq n}\sum _{j\neq k}X_{ij}X_{ik}\right)=n\cdot {\frac {1}{k}}+n(n-1)\cdot {\frac {1}{k^{2}}}={\frac {n^{2}+nk-n}{k^{2}}}}$

Finalmente, la complejidad sería . ${\displaystyle O\left(\sum _{i=1}^{k}E(n_{i}^{2})\right)=O\left(\sum _{i=1}^{k}{\frac {n^{2}+nk-n}{k^{2}}}\right)=O\left({\frac {n^{2}}{k}}+n\right)}$

El último paso de la clasificación de depósitos, que consiste en concatenar todos los objetos ordenados en cada depósito, requiere tiempo. Por tanto, la complejidad total es . Tenga en cuenta que si se elige k como , entonces la clasificación por depósitos se ejecuta en un tiempo promedio, dada una entrada distribuida uniformemente. ^[1] ${\displaystyle O(k)}$ ${\displaystyle O\left(n+{\frac {n^{2}}{k}}+k\right)}$ ${\displaystyle k=\Theta (n)}$ ${\displaystyle O(n)}$

Optimizaciones

Una optimización común es colocar primero los elementos no ordenados de los depósitos en la matriz original y luego ejecutar la ordenación por inserción en 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]

Si la distribución de entrada se conoce o se puede estimar, a menudo se pueden elegir cubos que contengan densidad constante (en lugar de simplemente tener un tamaño constante). Esto permite una complejidad de tiempo promedio incluso sin entradas distribuidas uniformemente. ${\displaystyle O(n)}$

Variantes

Clasificación de cubos genéricos

La variante más común de clasificación de depósitos 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 depósitos, cada uno de ellos de tamaño M / n . Si cada depósito se ordena mediante 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 muchos valores aparecen juntos, todos caerán en un solo grupo y se clasificarán lentamente. Esta degradación del rendimiento se evita en el algoritmo de clasificación de depósitos original suponiendo que la entrada se genera mediante un proceso aleatorio que distribuye elementos uniformemente en el intervalo [0,1) . ^[1]

Ordenar mapaprox

De manera similar a la clasificación de depósitos genérica descrita anteriormente, ProxmapSort funciona dividiendo una matriz de claves en submatrices mediante el uso de una función de "mapa de claves" que conserva un orden parcial de las claves; A medida que se agrega cada clave a su submatriz, se utiliza la ordenación por inserción para mantener ese submatriz ordenado, lo que da como resultado que toda la matriz esté ordenada cuando se completa ProxmapSort. ProxmapSort se diferencia de la clasificación de depósitos en el uso de la clave del mapa para colocar los datos aproximadamente donde pertenecen en orden, produciendo un "proxmap" (un mapeo de proximidad) de las claves.

Ordenación de histograma

Otra variante de la clasificación por depósitos conocida como clasificación por histograma o clasificación por conteo agrega un paso inicial que cuenta la cantidad de elementos que caerán en cada depósito utilizando una matriz de conteo. ^[4] Usando esta información, los valores de la matriz se pueden organizar en una secuencia de depósitos en el lugar mediante una secuencia de intercambios, sin dejar espacio adicional para el almacenamiento del depósito. ^{[ verificación fallida ]}

Tipo de cartero

La clasificación del cartero es una variante de la clasificación por cubos que aprovecha una estructura jerárquica de elementos, normalmente descrita por un conjunto de atributos. Éste 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 depósitos. Esto es similar a una clasificación por 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 por cubos que comienza eliminando el primer 1/8 de los n elementos a ordenar, los clasifica 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 artículos. Luego, cada "depósito" se ordena 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 depósito tiene tamaño 1, la clasificación por depósito degenera a clasificación por conteo. El tamaño de depósito variable de la clasificación de depósitos le permite utilizar memoria O( n ) en lugar de memoria O( M ), donde M es el número de valores distintos; a cambio, deja de contar el peor comportamiento de tipo O( n + M ).

La clasificación por depósitos con dos depósitos es efectivamente una versión de clasificación rápida en la que el valor de pivote siempre se selecciona para que sea el valor medio del rango de valores. Si bien esta elección es efectiva para entradas distribuidas uniformemente, otros medios para elegir el pivote en la clasificación rápida, como los pivotes seleccionados aleatoriamente, lo hacen más resistente a la agrupación en la distribución de entradas.

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 se pueden volver a combinar mediante una simple concatenación como en la clasificación por depósitos. En lugar de ello, deben intercalarse mediante un algoritmo de fusión. Sin embargo, este gasto adicional se ve contrarrestado por 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 clasificación de base de arriba hacia abajo puede verse como un caso especial de clasificación de depósitos en el que tanto el rango de valores como el número de depósitos 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 categoría.

Referencias

1. 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 clasificación por conteo, la clasificación por cubos es rápida porque supone algo sobre la entrada. Mientras que la clasificación por conteo supone que la entrada consta de números enteros en un rango pequeño, la clasificación por cubo supone que la entrada se genera mediante un proceso aleatorio que distribuye los elementos uniformemente en el intervalo [0,1) . La idea de la clasificación de depósitos es dividir el intervalo [0, 1) en n subintervalos o depósitos del mismo tamaño y luego distribuir los n números de entrada en los depósitos. Dado que las entradas están distribuidas uniformemente en [0, 1) , no esperamos que caigan muchos números en cada grupo. Para producir el resultado, simplemente ordenamos los números en cada depósito y luego revisamos los depósitos en orden, enumerando los elementos de cada uno.
2. Corwin, E. y Logar, A. "Clasificación en tiempo lineal: variaciones en la clasificación por cubos". Revista de Ciencias de la Computación en las Universidades , 20, 1, págs.197–202. Octubre de 2004.
3. 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áginas 174-177. 
4. Diccionario de algoritmos y estructuras de datos del NIST: clasificación de histogramas
5. "Desarrollo de software de Robert Ramey".
6. Un nuevo tipo revolucionario de John Cohen 26 de noviembre de 1997

• Paul E. Black "Clasificación del cartero" del Diccionario de algoritmos y estructuras de datos del NIST .
• Diario de usuarios de C "The Postman's Sort" de Robert Ramey, agosto de 1992
• Diccionario de algoritmos y estructuras de datos del NIST: clasificación de cubos

enlaces externos

• Código de clasificación de cucharón para Ansi C
• Variante de clasificación de cubos con demostración