Ordenar por cubos

Algoritmo de ordenación

Los elementos se distribuyen entre contenedores

Luego, los elementos se clasifican dentro de cada contenedor.

El ordenamiento por cubos , o bin sort , es un algoritmo de ordenamiento que funciona distribuyendo los elementos de una matriz en varios cubos. Luego, cada cubo se ordena individualmente, ya sea utilizando un algoritmo de ordenamiento diferente o aplicando recursivamente el algoritmo de ordenamiento por cubos. Es un ordenamiento por distribución , una generalización del ordenamiento por casillero que permite múltiples claves por cubo, y es un primo del ordenamiento por radix en el estilo de dígito más significativo a menos significativo. El ordenamiento por cubos se puede implementar con comparaciones y, por lo tanto, también se puede considerar un algoritmo de ordenamiento por comparación . La complejidad computacional depende del algoritmo utilizado para ordenar cada cubo, la cantidad de cubos a utilizar y si la entrada se distribuye uniformemente.

La ordenación por cubos funciona de la siguiente manera:

1. Configurar una matriz de "cubos" inicialmente vacíos.
2. Dispersión : recorre la matriz original, colocando cada objeto en su contenedor.
3. Ordena cada cubo que no esté vacío.
4. Recopilar : visita los contenedores en orden y vuelve 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 ← 1 + el valor máximo de la clave en la matriz para i = 0 a length(array) hacer insertar array[i] en buckets[floor(k × array[i] / M)]  para i = 0 a k hacer  siguienteSort(cubos[i]) devuelve la concatenación de buckets[0], ...., buckets[k]

Sea array la matriz que se va a ordenar y k la cantidad de contenedores que se van a utilizar. Se puede calcular el valor máximo de la clave en tiempo lineal iterando sobre todas las claves una vez. La función floor debe utilizarse para convertir un número flotante en un entero (y posiblemente también para la conversión de tipos de datos). La función nextSort es una función de ordenación que se utiliza para ordenar cada contenedor. Convencionalmente, se utiliza la ordenación por inserción , pero también se pueden utilizar otros algoritmos, como la ordenación por selección o la ordenación por fusión . El uso de bucketSort como nextSort produce un relativo de la ordenación por radix ; 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 que están cerca unas de otras (agrupamiento), es probable que esos elementos se coloquen en el mismo contenedor, lo que da como resultado que algunos contenedores contengan más elementos que el promedio. El peor escenario ocurre cuando todos los elementos se colocan en un solo contenedor. El rendimiento general estaría entonces dominado por el algoritmo utilizado para ordenar cada contenedor, por ejemplo, algoritmos de ordenación por inserción o de ordenación por comparación , como la ordenación por combinación . ${\displaystyle O(n^{2})}$ ${\displaystyle O(n\log(n))}$

Análisis de casos promedio

Considere el caso en el que la entrada se distribuye uniformemente. El primer paso, que es inicializar los contenedores y encontrar el valor de clave máximo en la matriz, se puede realizar en el tiempo. Si la división y la multiplicación se pueden realizar en tiempo constante, entonces la dispersión de cada elemento en su contenedor también cuesta . Suponga que se utiliza la ordenación por inserción para ordenar cada contenedor, entonces el tercer paso cuesta , donde es la longitud del contenedor indexado . Dado que nos ocupamos del tiempo promedio, la expectativa debe evaluarse en su lugar. Sea la variable aleatoria que es si el elemento se coloca en el contenedor , 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 la suma en el caso y el caso . Dado que la probabilidad de que un objeto se distribuya en el cubo es , 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 quedaría

${\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 del ordenamiento por cubos, que consiste en concatenar todos los objetos ordenados en cada cubo, requiere tiempo. Por lo tanto, la complejidad total es . Nótese que si se elige que k sea , entonces el ordenamiento por cubos 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 poner primero los elementos no ordenados de los contenedores nuevamente en la matriz original y 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, la cantidad de comparaciones sigue siendo relativamente pequeña y la jerarquía de memoria se aprovecha mejor almacenando la lista de manera contigua en la memoria. ^[2]

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

Variantes

Ordenación de cubos genéricos

La variante más común de ordenación por cubos opera sobre una lista de n entradas numéricas entre cero y un valor máximo M y divide el rango de valores en b cubos, cada uno de tamaño M / b . Si cada cubo se ordena utilizando la ordenación por inserción , se puede demostrar que la ordenación se ejecuta en el tiempo lineal esperado (donde se toma el promedio sobre todas las entradas posibles). ^[3] Sin embargo, el rendimiento de esta ordenación se degrada con la agrupación; si muchos valores ocurren juntos, todos caerán en un solo cubo y se ordenarán lentamente. Esta degradación del rendimiento se evita en el algoritmo de ordenación por cubos original al suponer que la entrada se genera mediante un proceso aleatorio que distribuye los elementos de manera uniforme en el intervalo [0,1) . ^[1]

Ordenar por mapas de proximidad

De manera similar a la ordenación por cubos genérica descrita anteriormente, ProxmapSort funciona dividiendo una matriz de claves en submatrices mediante el uso de una función de "clave de mapa" 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 esa submatriz ordenada, lo que da como resultado que toda la matriz esté en orden ordenado cuando ProxmapSort se completa. ProxmapSort se diferencia de las ordenaciones por cubos en el uso de la clave de mapa para colocar los datos aproximadamente donde pertenecen en el orden ordenado, lo que produce un "proxmap" (un mapeo de proximidad) de las claves.

Ordenación por histograma

Otra variante de la clasificación de cubos, conocida como clasificación de histograma o clasificación por conteo , agrega un paso inicial que cuenta la cantidad de elementos que caerán en cada cubo usando una matriz de conteo. ^[4] Usando 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 adicional para el almacenamiento de cubos. ^{[ verificación fallida ]}

Tipo de cartero

El método de clasificación del cartero es una variante del método de clasificación por cubos que aprovecha una estructura jerárquica de elementos, normalmente descrita por un conjunto de atributos. Este es el algoritmo que utilizan las máquinas de clasificación de cartas en las oficinas postales : el correo se clasifica primero entre nacional e internacional; luego por estado, provincia o territorio; luego por oficina postal de destino; luego por rutas, etc. Como 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 un método de clasificación por radix que funciona "de arriba hacia abajo" o "primero el dígito más significativo". ^[5]

Ordenación aleatoria

El ordenamiento aleatorio ^[6] es una variante del ordenamiento por cubos que comienza eliminando los primeros 1/8 de los n elementos que se ordenarán, los ordena recursivamente y los coloca en una matriz. Esto crea n /8 "cubos" entre los cuales se distribuyen los 7/8 restantes de los elementos. Luego se ordena cada "cubo" y los "cubos" se concatenan en una matriz ordenada.

Comparación con otros algoritmos de ordenación

La ordenación por cubos puede considerarse una generalización de la ordenación por conteo ; de hecho, si cada cubo tiene un tamaño de 1, la ordenación por cubos degenera en ordenación por conteo. El tamaño variable de cubo de la ordenación por cubos le permite utilizar memoria O( n ) en lugar de memoria O( M ), donde M es la cantidad de valores distintos; a cambio, renuncia al comportamiento en el peor de los casos de la ordenación por conteo O( n + M ).

La ordenación por cubos con dos cubos es, en efecto, una versión de la ordenación rápida en la que el valor pivote siempre se selecciona como el valor medio del rango de valores. Si bien esta opción es eficaz para entradas distribuidas de manera uniforme, otros medios de elegir el pivote en la ordenación rápida, como los pivotes seleccionados aleatoriamente, hacen que sea más resistente a la agrupación en la distribución de entrada.

El algoritmo de ordenación por fusión de n vías también comienza distribuyendo la lista en n sublistas y ordenando cada una de ellas; sin embargo, las sublistas creadas por ordenación por fusión tienen rangos de valores superpuestos y, por lo tanto, no se pueden volver a combinar mediante una simple concatenación como en la ordenación por cubos. En cambio, se deben intercalar mediante un algoritmo de combinació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.

El ordenamiento por radix de arriba hacia abajo puede considerarse un caso especial de ordenamiento por cubetas, en el que tanto el rango de valores como la cantidad de cubetas se limitan a una potencia de dos. En consecuencia, el tamaño de cada cubeta 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 en bits de cada elemento para determinar su cubeta.

Referencias

1. Thomas H. Cormen ; Charles E. Leiserson ; Ronald L. Rivest & Clifford Stein . Introducción a los algoritmos . La ordenación por cubos se ejecuta en tiempo lineal en promedio. Al igual que la ordenación por conteo, la ordenación por cubos es rápida porque supone algo sobre la entrada. Mientras que la ordenación por conteo supone que la entrada consiste en 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 ordenación por cubos es dividir el intervalo [0, 1) en n subintervalos o cubos de igual tamaño 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 cubo. Para producir el resultado, simplemente ordenamos los números en cada cubo y luego los recorremos en orden, enumerando los elementos en cada uno.
2. Corwin, E. y Logar, A. "Ordenamiento en tiempo lineal: variaciones del ordenamiento por cubos". Journal of Computing Sciences in Colleges , 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 por cubos, págs. 174-177. 
4. Diccionario de algoritmos y estructuras de datos del NIST: ordenación por histograma
5. "Desarrollo de software de Robert Ramey".
6. Una nueva forma revolucionaria de escribir de John Cohen 26 de noviembre de 1997

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

Enlaces externos

• Código de clasificación de contenedores para ANSI C
• Variante de clasificación por cubos con demostración